正整数のゲーデル数化？ in StandardML DouKaku?

正の整数 n を引数としてとり， 2^d1 * 3^d2 * 5^d3 ... * pk^dk を返す関数
goedel を定義してください．

ただし，n を10進表現で k 桁の数としたときの各桁の数が数列 [d1,d2,d3,...,dk]
をなすとし，dk が 1 の位，d1 が 10^(k-1) の位です．また，pk は k番目の素数です．

goedel   9  ⇒ 2^9             ⇒  512
goedel  81  ⇒ 2^8 * 3^1       ⇒  768
goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108

see: ゲーデル数

10桁限定。それ以上は整数がoverflowします。

fun prime n a 0 = a
  | prime n a i =
  if n mod 2 <> 0 andalso n mod 3 <> 0 then
    prime (n + 1) (a @ [n]) (i - 1)
  else
    prime (n + 1) a i


fun goedel n =
let
  val p = prime 5 [2, 3] 10
  val a = map (valOf o Int.fromString o str) ((explode o Int.toString) n)
in
  floor (ListPair.foldl (fn (x, y, z) => Math.pow (real x, real y) * z) 1.0 (p, a))
end

val printInt = println o Int.toString;

printInt (goedel 9);
printInt (goedel 81);
printInt (goedel 230)

素数生成が間違っていたので修正。ついでに多倍長整数を使って、Overflowしないようにしてみた。

fun prime n =
let
  val a = List.tabulate (n - 1, fn x => x + 2)

  fun loop [] = []
    | loop (x::xs) =
      x :: loop (List.filter (fn i => i mod x <> 0) xs)
in
  loop a
end


fun goedel (n : IntInf.int) =
let
  open IntInf

  val p = map fromInt (prime 100)
  val a = map (valOf o Int.fromString o str) ((explode o toString) n)
in
  toString (ListPair.foldl (fn (x, y, z) => pow (x, y) * z) 1 (p, a))
end


fun println s = print (s ^ "\n")

val _ = println (goedel 9)
val _ = println (goedel 81)
val _ = println (goedel 230)
val _ = println (goedel 19425463134)

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - StandardML

Index

Feed

Other

Link

Pathtraq