正整数のゲーデル数化？ in OCaml 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: ゲーデル数

特にひねりのない実装。
素数はエラトステネスのふるいを使ったジェネレータにしてますが、
工夫のない作りなのでたぶん指数オーダーです。

最近は関数型至上主義も薄れてきて、リファレンスや for 文なども
わりと平気で使えるようになってきました。
外に影響出さないなら、中で何やってたって良いんです :-p


% ocaml goedel.ml
goedel 9 => 2^9 => 512
goedel 81 => 2^8 * 3^1 => 768
goedel 230 => 2^2 * 3^3 * 5^0 => 108

let gen_prime () =
   let now = ref 2 in
   let buf = ref [2] in
   let rec is_prime = function
      | 2 -> true
      | n ->
           if List.exists (fun i -> n mod i = 0) !buf
           then false
           else (buf := n::!buf; true)
   in
   let rec next_prime i =
      let n = !now in
      incr now;
      if is_prime n
      then Some n
      else next_prime i
   in
   Stream.from next_prime

let goedel n =
   let pow n = function
      | 0 -> 1
      | m ->
           let rec loop acc = function
              | 1  -> acc
              | m' -> loop (acc * n) (m' - 1)
           in
           loop n m
   in
   let s      = string_of_int n in
   let buf    = Buffer.create 10 in
   let add    = Buffer.add_string buf in
   let result = ref 1 in
   let primes = gen_prime () in
   for i = 0 to (String.length s) - 1 do
      let m = int_of_string (String.make 1 s.[i]) in
      let n = Stream.next primes in
      if Buffer.length buf > 0 then add " * ";
      List.iter add [string_of_int n; "^"; string_of_int m];
      result := !result * (pow n m)
   done;
   (Buffer.contents buf, !result)

let test () =
   let samples = [9; 81; 230] in
   List.iter begin fun n ->
      let s, r = goedel n in
      Printf.printf "goedel %d => %s => %d\n" n s r
   end samples

let () = if not !Sys.interactive then test ()

なんとなく大きな数対応版 (Num モジュール使用)。
素数の方はたかだか数十番目くらいしか必要にならないので int のまま。

% ocaml nums.cma goedel.ml
goedel 9 => 2^9 => 512
goedel 81 => 2^8 * 3^1 => 768
goedel 230 => 2^2 * 3^3 * 5^0 => 108
goedel 1256 => 2^1 * 3^2 * 5^5 * 7^6 => 6617756250
goedel 34721 => 2^3 * 3^4 * 5^7 * 7^2 * 11^1 => 27286875000
goedel 542673 => 2^5 * 3^4 * 5^2 * 7^6 * 11^7 * 13^3 => 326393949142783922400
goedel 19425463134 => 2^1 * 3^9 * 5^4 * 7^2 * 11^5 * 13^4 * 17^6 * 19^3 * 23^1 * 29^3 * 31^4 => 475616767259341262526341725017954602561250

open Num

let gen_prime () =
   let now = ref 3 in
   let buf = ref [2] in
   let rec is_prime = function
      | 2 -> true
      | n ->
           let limit = n / 2 in
           if List.exists begin fun i ->
              if i > limit
              then false (* skip *)
              else n mod i = 0
           end !buf
           then false
           else (buf := n::!buf; true)
   in
   let rec next_prime = function
      | 0 -> Some 2
      | i ->
         let n = !now in
         now := !now + 2;
         if is_prime n
         then Some n
         else next_prime i
   in
   Stream.from next_prime

let goedel num =
   let s      = string_of_num num in
   let buf    = Buffer.create 10 in
   let add    = Buffer.add_string buf in
   let result = ref (Int 1) in
   let primes = gen_prime () in
   for i = 0 to (String.length s) - 1 do
      let cs = String.make 1 s.[i] in
      let m  = num_of_string cs in
      let n  = Stream.next primes in
      if Buffer.length buf > 0 then add " * ";
      List.iter add [string_of_int n; "^"; cs];
      result := !result */ (power_num (Int n) m)
   done;
   (Buffer.contents buf, !result)

let test () =
   let samples = [9; 81; 230; 1256; 34721; 542673; 19425463134] in
   let pr ch n = output_string ch (string_of_num n) in
   List.iter begin fun n ->
      let s, r = goedel (Int n) in
      Printf.printf "goedel %a => %s => %a\n" pr (Int n) s pr r
   end samples

let () = if not !Sys.interactive then test ()

セルフprimeで。
デフォルト値を変更するときは
goedel ~prime:[|1.; 2.; 3.|] n とか
goedel ~prime:(gen_prime x) n のようにして使います。

let goedel ?(prime=[|2.; 3.; 5.; 7.; 11.|]) n =
  let res = ref 1. in
  let i = ref 0 in (*iteri用*)
  String.iter
    (fun x -> 
      res := !res *. (prime.(!i) ** (float_of_string (Char.escaped x)) );
      incr i)
    (string_of_int n);
  res.contents;;

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - OCaml

Index

Feed

Other

Link

Pathtraq