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

こうかな？
c=2が美しく無いけど。

def goedel(n):
    result = 1
    c = 2
    for x in str(n):
        result *= c**int(x)
        c += 1
    return result

print goedel(9)
print goedel(81)
print goedel(230)

全力で問題を勘違いしていた。
素数を生成する部分を追加してみた。

def CreatePrimes(n):
    primes = []
    c = 2
    while len(primes) < n:
        primes.append(c)
        for x in primes[:-1]:
            if c%x == 0:
                primes.pop();
                break
        c += 1
    return primes

def goedel(n):
    result = 1
    primes = CreatePrimes(len(str(n)))
    
    for x in str(n):
        result *= primes[0]**int(x)
        primes = primes[1:]
    return result

print goedel(9)
print goedel(81)
print goedel(230)
print goedel(12345)

こんな感じでしょうか。IEnumerator<int> がなんか気持ち悪いですが……

using System;
using System.Collections.Generic;
static class Program {
    static void Main() {
        Console.WriteLine(Goedel(9));   // 512
        Console.WriteLine(Goedel(81));  // 768
        Console.WriteLine(Goedel(230)); // 108
    }
    static double Goedel(int num) {
        double goedel = 1;
        IEnumerator<int> p = Prime();
        foreach(char c in num.ToString()) {
            p.MoveNext();
            goedel *= Math.Pow(p.Current, c - '0');
        }
        return goedel;
    }
    static IEnumerator<int> Prime() {
        yield return 2;
        List<int> primes = new List<int>();
        for(int num = 3; ; num += 2) {
            foreach(int p in primes) {
                if (num % p == 0)
                    goto SKIP;
            }
            primes.Add(num);
            yield return num;
        SKIP:;
        }
    }
}

n を 10 桁までに限定しています。

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int goedel( int n ){
   static int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
   char buf[11];
   char *dk = buf;
   int *pk = prime;
   int result = 1;
   snprintf(dk,11,"%d",n);
   while(*dk){
      result *= pow( *pk++, *dk++ -'0' );
   }
   return result;
}

void main ( void ){
   printf("%d\n", goedel(9));
   printf("%d\n", goedel(81));
   printf("%d\n", goedel(230));
}

もうちょっと簡単に出来そう

use strict;
use warnings;
use Math::Prime::XS qw(is_prime);
use List::Util qw(reduce);
use List::MoreUtils qw(pairwise);

sub primes {
    my $number = shift;
    my @primes = (2);
    my $i      = 3;
    while ( @primes < $number ) {
        push( @primes, $i ) if is_prime($i);
        $i++;
    }
    return @primes;
}

sub goedel {
    my $number = shift;
    my @num    = split //, $number;
    my @primes = primes( scalar(@num) );
    reduce { $a * $b } pairwise { $a**$b } @primes, @num;
}

print goedel(9);
print goedel(81);
print goedel(230);

Squeak Smalltalk で。

指定した数未満の素数列を生成する、組み込みの Integer class>>#primesUpTo: を流用して富豪的に。

| primesOfSize goedel |

primesOfSize := [:n |
    | m primes  |
    m := 0.
    [(primes := Integer primesUpTo: (10 raisedTo: (m := m + 1))) size >= n] whileFalse.
    primes first: n].

goedel := [:num |
    | digits size |
    digits := (num asString as: Array) collect: [:char | char asString asInteger].
    size := digits size.
    primes := primesOfSize value: size.
    (1 to: size) inject: 1 into: [:goe :idx | goe * ((primes at: idx) raisedTo: (digits at: idx))]].

goedel value: 9.   "=> 512 "
goedel value: 81.   "=> 768 "
goedel value: 230.   "=> 108 "

やっぱり一度文字列化するの一番効率的で簡単みたいです。

import Data.Char

primes = sieve [2..] 
  where 
  sieve (x:xs) = x : sieve [y| y<-xs, y `mod` x /= 0]

goedel x = product $ zipWith (^) primes (map digitToInt (show x))

{-
*Main> goedel 9
512
*Main> goedel 81
768
*Main> goedel 230
108
-}

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)

あれ、これだと

goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108
goedel 23   ⇒ 2^2 * 3^3 ⇒  108

なので、ゲーデル数と元の数との一対一対応が取れないのでは?

こうすればOKだけど

goedel' 230  ⇒ 2^(2+1) * 3^(3+1) * 5^(0+1) ⇒  3240
goedel' 23   ⇒ 2^(2+1) * 3^(3+1) ⇒  648

Dan the Goedel Numberer

goedel_number()の二番目の引数にnonzeroを指定することで#4657で指摘した「仕様バグ」にも対応しています。

Dan the Goedel Numberer

#!/usr/local/bin/perl
use strict;
use warnings;

my @primes = ( 2, 3 );

sub fill_primes {
    my $nprimes = shift;
  ODD:
    for ( my $n = $primes[ @primes - 1 ] + 2 ; @primes < $nprimes ; $n += 2 ) {
        for my $d (@primes) {
            last if $d * $d > $n;
            next ODD unless $n % $d;
        }
        push @primes, $n;
    }
}

sub goedel_number {
    my $n      = shift;
    my $offset = shift || 0;
    my @d      = ( $n =~ /(\d)/g );
    fill_primes( scalar @d );
    use bigint;
    my $result = 1;
    $result *= $primes[$_]**( $d[$_] + $offset ) for ( 0 .. @d - 1 );
    $result;
}

local $\ = "\n";
local $, = ", ";
print goedel_number( $ARGV[0] || 1234567890, $ARGV[1] );

#4658の素直な移植。

Dan the Goedel Numberer

var primes = [2,3];
function fill_primes(nprimes){
  function f(n){
    for (var p = 0, l = primes.length; p < 0; p++){
      if (p*p > n)    return;
      if (n % d == 0) break;
    }
    primes[primes.length] = n;
  }
  for (var n = primes[primes.length-1]+2; primes.length < nprimes; n += 2)
    f(n);
}
function goedel_number(n, offset){
  if (! offset) offset = 0;
  var d = [];
  n.toString().replace(/\d/g, function(m){
    d[d.length] = parseInt(m);
  });
  fill_primes(d.length);
  var result = 1;
  for (var i = 0, l = d.length; i < l ; i++) {
    result *= Math.pow(primes[i], d[i]+offset);
  }
  return result;
}
/*
p(goedel_number(23));
p(goedel_number(230));
p(goedel_number(23,1));
p(goedel_number(230,1));
*/

車輪は発明しない方向で。

require "mathn"
def goedel(n)
  prime=Prime.new
  n.to_s.split(//).inject(1){|r,k| r*=prime.next**k.to_i}
end

ゲーテル数の定義とは関係ないですが、
一対一対応を素直に取れるように定義を変更するなら、
逆向きに並べるのが単純でいい気がします。

goedel 230  ⇒ 2^2 * 3^3 * 5^0 ⇒  108
goedel  23  ⇒ 2^2 * 3^3 ⇒  108

ではなく、

goedel 230  ⇒ 2^0 * 3^3 * 5^2 ⇒  675
goedel  23  ⇒ 2^3 * 3^2 * 5^0 ⇒  72

これで、位取りの意味的に上位の0は無視することと、
0乗した値が無視できることが対応づけられます。

素朴に。

import itertools

def is_prime(n):
    for i in itertools.count(2):
        if i * i > n:
            return True
        if n % i == 0:
            return False

def primes():
    for n in itertools.count(2):
        if is_prime(n):
            yield n

def numbers(n):
    a = []
    while n:
        a.append(n % 10)
        n /= 10
    return reversed(a)

def goedel(n):
    result = 1
    for pk, dk in itertools.izip(primes(), numbers(n)):
        result *= (pk ** dk)
    return result

def main():
    for n in (9, 81, 230):
        print goedel(n)

if __name__ == '__main__':
    main()

素数を作るところをもっとなんとかしたい・・・。とりあえず出来たのでUP。

see: エラトステネスの篩 - Wikipedia

<?php
function prime($len)
{
    $result = array(2);
    for($n = 2; $n <= $len; $n++) {
        if($n % 2 == 0) {
            continue;
        }
        for($i = 3 ; pow($i, 2) <= $n ; $i += 2) {
            if($n % $i == 0)
                continue 2;
        }
        array_push($result, $n);
    }
    return $result;
}

function goedel($n)
{
    $n = strval($n);
    $result = 1;
    $prime = prime($n);
    for($i = 0; $i < strlen($n); $i++) {
        $result *= pow($prime[$i], $n[$i]);
    }
    return $result;
}

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

最近は関数型至上主義も薄れてきて、リファレンスや 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 ()

とりあえず，「仕様バグ」は無視して題意どおりの実装。

$ java Goedel 230
108

$ java Goedel 123456789
52713275010243038997421106186697438702252144407250

import java.math.BigInteger;
import java.util.Vector;

public class Goedel {
    private static final int CERTAINTY = 24;
    public static void main(String[] args) throws Exception {
        Vector<BigInteger> primes = new Vector<BigInteger>();
        for (int i = 2; primes.size() < args[0].length(); i++) {
            BigInteger bi = BigInteger.valueOf(i);
            if (bi.isProbablePrime(CERTAINTY)) primes.add(bi);
        }
        BigInteger result = BigInteger.ONE;
        for (int i = 0; i < args[0].length(); i++)
            result = result.multiply(primes.get(i).pow(Integer.valueOf(args[0].substring(i,i+1))));
        System.out.println(result);
    }
}

なんとなくstreamを使ってみた。 sieveとprimesはSICPのやつ。

(use util.stream)
(use gauche.collection)

(define (integers-starting-from n)
  (stream-cons n (integers-starting-from (+ n 1))))

(define (sieve stream)
  (define (divisible? x y) (= (remainder x y) 0))
  (stream-cons
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x) (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

(define (number->digit-stream n)
  (stream-map
   (lambda (c) (- (char->integer c) (char->integer #\0)))
   (string->stream (number->string n))))

(define (goedel n)
  (apply * (stream->list
            (stream-map (lambda (pk nk) (expt pk nk))
                        primes (number->digit-stream n)))))

所詮は浮動小数点数なので大きなnについての精度は無考慮。

primes(100)は100までの素数25個を返す。 25と決めうちしているのは気持ち悪いが、double型が正確に表わせるのは高々十数桁であり、その範囲で使うぶんにはとりあえずはOKとする。桁数に応じた数の素数をとりだしたい場合は、第4行を次のように置き換えればよい:

if n < 6
  p = primes(11);  % Five smallest primes
else
  u = n*(log(n) + log(log(n)));  % An upper bound of the value of the nth prime
  p = primes(u);
end

上界uはピエール・デザルトの定理による。

function g = goedel(n)
  s = num2str(n) - '0';
  n = length(s);
  p = primes(100);
  g = prod(p(1:n).^s);

で、結局ゲーデル数って何ですか?(w

see: 貧脚レーサーのサボり日記

//http://ja.doukaku.org/100/　投稿用
using System;
using System.Collections.Generic;
class Program {
　　static void Main(string[] args) {
　　　　Console.WriteLine(goedel(9));
　　　　Console.WriteLine(goedel(81));
　　　　Console.WriteLine(goedel(230));
　　　　Console.ReadLine();
　　}

　　static double goedel(int n) {
　　　　string tmpStr = n.ToString();
　　　　double r = 1;
　　　　List<double> prime = new List<double>(new double[] { 2 });
　　　　for(int i = 3; ; i += 2) {
　　　　　　bool isPrime = true;
　　　　　　for(int j = 3; j < i; j++) {
　　　　　　　　if(i % j == 0) {
　　　　　　　　　　isPrime = false;
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　}
　　　　　　if(isPrime) prime.Add(i);
　　　　　　if(prime.Count >= tmpStr.Length) break;
　　　　}
　　　　for(int i = 0; i < tmpStr.Length; i++) {
　　　　　　r *= Math.Pow(prime[i], (double.Parse(tmpStr[i].ToString())));
　　　　}
　　　　return r;
　　}
}

とりあえずお題通りに（桁が変わると一意じゃないのを見越してタイトルに？が付いてるのと解釈）。とりあえず解が出せるのは5桁までかな....6桁だと64bitでも溢れる気がする。桁数が少ないので素数は計算せず。

#include <complex>

static unsigned int prime[] = {2, 3, 5, 7, 11};

unsigned int digit(unsigned int n, unsigned int base)
{
    unsigned d = 1;
    for (; n > (base - 1); n /= base) { d++; }
    return d;
}

unsigned long long goedel(unsigned int n)
{
    unsigned long long ans = 1;
    for (unsinged int d = digit(n, 10); d > 0; d--, n /= 10)
        ans *= (unsigned long long)std::pow((double)prime[d - 1], (int)(n % 10));
    return ans;
}

計算違い。4桁で既に溢れてる....orz

仕様通りに組んでみました

!変数宣言が必要
●CPrime(N)
    PrimeListとは配列=2
    Flagとは整数=0
    Mとは整数=2
    Iとは整数
    (要素数(PrimeList)<N)の間
        Iで2からINT(SQRT(M))+1まで繰り返す
            もし(M%I=0)ならば
                Flag=1
                抜ける
        もし(Flag=0)ならば
            PrimeListにMを配列追加
        Flag=0
        M=M+1
    PrimeListで戻る
●goedel(N)
    TMPとは整数=1
    NListとは配列=文字列分解(TOSTR(N))
    PrimeListとは配列=CPrime(N)
    PrimeListを反復
        TMP=TMP*(対象^NList[回数-1])
    TMPで戻る

goedel(9)を表示
goedel(81)を表示
goedel(230)を表示

nobreak 便利。

doukaku100: fun(n){
  primes: fiber(){
    yield 2;
    for(n: 3;; n += 2)
      for(d, m : 3, math::sqrt(n); d < m; d += 2)
        if(n % d == 0) break; nobreak yield n;
  }
  r: 1;
  n.to_s.split("").zip(primes){|d, p| r *= math::pow(p, d.to_i); }
  return r;
}

なんとなく大きな数対応版 (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 ()

素数生成が間違っていたので修正。ついでに多倍長整数を使って、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)

ちょっとparallel list comprehension使ってみたかったんので...。 zipWith (^)より可読性いいかもしれないですね。

{-# OPTIONS_GHC -fglasgow-exts #-}
import Data.Char

primes = sieve [2..] 
  where 
  sieve (x:xs) = x : sieve [y| y<-xs, y `mod` x /= 0]

goedel x = product [p^(digitToInt c) | p <- primes | c <- show x]

{-
*Main> goedel 9
512
*Main> goedel 81
768
*Main> goedel 230
108
-}

import std.conv;
import std.math;
import std.string;

uint goedel(uint n) {
        static int[] primes = [ 2, 3 , 5, 7, 11, 13, 17, 19, 23, 29 ];
        real rslt = 1;
        string str = toString(n);
        for (int i = 0; i < str.length; ++i) {
                rslt *= pow(cast(real)(primes[i]), toUint([str[i]]));
        }
        return cast(uint)(rslt);
}

/*
import std.stdio;

void main() {
        writefln("%d, %d, %d", 9, 512, goedel(9));
        writefln("%d, %d, %d", 81, 768, goedel(81));
        writefln("%d, %d, %d", 230, 108, goedel(230));
}
*/

この手の問題はMathematicaだと簡単に書けますね。

1	goedel[n_] := Times @@ MapIndexed[Prime[#2[[1]]]^#1 &, IntegerDigits[n]]

素数導出コードを書く気が起こりません。
無限精度整数がないのでやな感じです。

Module Module1

    Sub Main()
        Console.WriteLine(Goedel(9))
        Console.WriteLine(Goedel(81))
        Console.WriteLine(Goedel(230))
    End Sub

    Public Function Goedel(ByVal n As Integer) As Double
        If n < 0 Then Throw New ArgumentOutOfRangeException()
        Dim digits As New List(Of Integer)
        Dim primes As Integer()
        Dim r As Double

        While (n > 0)
            digits.Add(n Mod 10)
            n = n \ 10
        End While

        primes = GetPrimes(digits.Count)

        r = 1
        For i As Integer = 0 To digits.Count - 1
            r *= primes(i) ^ digits(digits.Count - i - 1)
        Next

        Return r
    End Function

    Public Function GetPrimes(ByVal count As Integer) As Integer()
        If count > 10 Then Throw New ArgumentOutOfRangeException()
        Dim r(count - 1) As Integer
        Array.Copy(PrimeSeeds, 0, r, 0, count)
        Return r
    End Function

    Private PrimeSeeds As Integer() = New Integer() {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

End Module

j言語です。
   goedel=.3 :'*/x:(p:i.#":y)^"."0":y'
   goedel 9
512
   goedel 81
768
   goedel 230
108
   goedel 12345
870037764750
   goedel 123456789
52713275010243038997421106186697438702252144407250


#4657の提案(goedel2)と#4661の提案(goedel3)もやってみました。
   goedel2=.3 :'*/x:(p:i.#":y)^>:"."0":y'
   goedel2 230
3240
   goedel2 23
648

   goedel3=.3 :'*/x:(p:i.#":y)^|."."0":y'
   goedel3 230
675
   goedel3 23
72

1	goedel=.3 :'*/x:(p:i.#":y)^"."0":y'

import java.lang.Double.parseDouble
def sieve(s: Stream[Int]): Stream[Int] =
  Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))
def primes = sieve(Stream.from(2))

def goedel(n:int) = {
  var s = n.toString
  primes.take(s.size).zipWithIndex.foldLeft(1d){(r, p) =>
    r*Math.pow(p._1, parseDouble(s(p._2)+""))
  }
}

普通に書くとイマイチ面白くないかと思ってひねり出したコード。牛刀割鶏な感はありますが、ジェネレータを使って繰り返しを行うマクロを定義して、これに素数ジェネレータを渡しています。これくらいだと Lisp マクロの入門用としていい題材だったかもしれません。

(defun make-prime-generator ()
  (let ((primes ()))
    (lambda ()
      (if (null primes)
          (setf primes (list 2))
        (do ((x (1+ (car primes)) (1+ x)))
            ((notany (lambda (p) (= (rem x p) 0)) primes)
             (push x primes))))
      (car primes))))

(defmacro loop-with-generator ((var generator)
                               (end-test &rest result) &body body)
  (let ((gvar (gensym)))
    `(do ((,gvar ,generator))
         (,end-test ,@result)
       (let ((,var (funcall ,gvar))) ,@body))))

(defun goedel (n)
  (let ((digits (do ((m n (floor m 10)) (ds ()))
                    ((= m 0) ds)
                  (push (rem m 10) ds)))
        (code 1))
    (loop-with-generator (p (make-prime-generator))
                         ((null digits) code)
      (setf code (* (expt p (pop digits)) code)))))

1> c(goedel).
{ok,goedel}
2> goedel:goedel(9).
512
3> goedel:goedel(81).
768
4> goedel:goedel(230).
108

-module(goedel).
-export([goedel/1]).

prime(Num) -> prime(Num - 1, [2], 3).

prime(0, List, _) -> lists:last(List);
prime(Num, List, Max) ->
    case lists:any(fun(X) -> (Max rem X) =:= 0 end, List) of
        true  -> prime(Num, List, Max + 2);
        false -> prime(Num - 1, List ++ [Max], Max + 2)
    end.

pow({_, 0}) -> 1;
pow({X, Y}) -> X * pow({X, Y - 1}).

column(Num) -> length(hd(io_lib:format("~B", [Num]))).

goedel(Num) ->
    List = [pow(X) || X <- goedel(Num, [], column(Num))],
    lists:foldl(fun(X, Proc) -> X * Proc end, 1, List).

goedel(_, List, 0) -> lists:zip([prime(X) || X <- lists:seq(1, length(List))], List);
goedel(Num, List, Size) -> goedel(Num div 10, [Num rem 10] ++ List, Size - 1).

ここでevalはどうなんだろう.

require "mathn"
def goedel(num)
  prime = Prime.new
  eval(num.to_s.scan(/\d/).map{|d| prime.next**d.to_i}.join('*'))
end

セルフ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;;

累乗は標準では定義されないので、自作しました。

<xsl:stylesheet version="2.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema"
  xmlns:fn="http://www.w3.org/2005/xpath-functions"
  xmlns:my="uri:ja.doukaku.org:my-functions"
  exclude-result-prefixes="my"
  >

  <xsl:output method="text" />

  <xsl:template match="/" >
    <xsl:text>geodel(9)=</xsl:text>
    <xsl:value-of select="my:goedel(9)" />
    <xsl:text>&#xA;goedel(81)=</xsl:text>
    <xsl:value-of select="my:goedel(81)" />
    <xsl:text>&#xA;goedel(230)=</xsl:text>
    <xsl:value-of select="my:goedel(230)" />
    <xsl:text>&#xA;</xsl:text>
  </xsl:template>

  <xsl:function name="my:goedel" as="xs:integer">
    <xsl:param name="n" as="xs:integer" />
    <xsl:if test="n&lt;=0">
      <xsl:message terminate="yes">
        n must be positive integer
      </xsl:message>
    </xsl:if>

    <xsl:variable name="n_" as="xs:string" select="xs:string($n)" />
    <xsl:variable name="primes" as="xs:integer*"
      select="my:primes(fn:string-length($n_))" />

    <xsl:variable name="elem" as="xs:integer*">
      <xsl:for-each select="fn:string-to-codepoints($n_)">
        <xsl:variable name="i" as="xs:integer"
          select="xs:integer(fn:codepoints-to-string((.)))" />
        <xsl:variable name="idx" as="xs:integer"
          select="position()" />
        <xsl:sequence select="my:power($primes[$idx],$i)" />
      </xsl:for-each>
    </xsl:variable>

    <xsl:value-of select="my:PI($elem)" />
  </xsl:function>

  <xsl:function name="my:power" as="xs:integer">
    <xsl:param name="n" as="xs:integer" />
    <xsl:param name="m" as="xs:integer" />

    <xsl:choose>
      <xsl:when test="$m=0">
        <xsl:value-of select="1" />
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$n*my:power($n,$m - 1)" />
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

  <xsl:function name="my:primes" as="xs:integer*">
    <xsl:param name="n" as="xs:integer" />

    <xsl:sequence select="my:primes_($n,2,())" />
  </xsl:function>

  <xsl:function name="my:primes_" as="xs:integer*">
    <xsl:param name="n" as="xs:integer" />
    <xsl:param name="m" as="xs:integer" />
    <xsl:param name="r" as="xs:integer*" />

    <xsl:choose>
      <xsl:when test="$n=0">
        <xsl:sequence select="$r" />
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="is_prime" as="xs:boolean"
          select="fn:empty($r[($m mod .)=0])" />
        <xsl:choose>
          <xsl:when test="$is_prime">
            <xsl:variable name="r_" as="xs:integer*">
              <xsl:sequence select="$r" />
              <xsl:sequence select="$m" />
            </xsl:variable>
            <xsl:sequence select="my:primes_($n - 1,$m + 1, $r_)" />
          </xsl:when>
          <xsl:otherwise>
            <xsl:sequence select="my:primes_($n,$m + 1, $r)" />
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>

  <xsl:function name="my:PI" as="xs:integer">
    <xsl:param name="seq" as="xs:integer*" />

    <xsl:choose>
      <xsl:when test="fn:empty($seq)" >
        <xsl:value-of select="0" />
      </xsl:when>
      <xsl:when test="fn:count($seq)=1">
        <xsl:value-of select="$seq[1]" />
      </xsl:when>
      <xsl:otherwise>
        <xsl:value-of select="$seq[1] * my:PI(fn:subsequence($seq,2))" />
      </xsl:otherwise>
    </xsl:choose>
  </xsl:function>
</xsl:stylesheet>

ちょっと付け足した部分がエラーになってた orz

24c24
<     <xsl:if test="n&lt;=0">
---
>     <xsl:if test="$n&lt;=0">

ストリームの練習も兼ねて。

(use srfi-1)
(use util.stream)

(define (goedel n)
  (let* ((ds (map digit->integer (string->list (number->string n))))
         (ps (stream->list (stream-take prime-stream (length ds)))))
    (fold * 1 (map expt ps ds))))

(define prime-stream
  (letrec ((sieve
            (lambda (strm)
              (let ((n (stream-car strm)))
                (stream-cons n
                             (sieve
                              (stream-remove (lambda (m)
                                               (zero? (remainder m n)))
                                             (stream-cdr strm))))))))
    (sieve (stream-iota -1 2))))

(define (main args)
  (print (goedel (string->number (cadr args))))
  0)

素数生成の部分はHaskellでは有名なコードなのでコピペです。

import List

goedel n = product $ zipWith (\p d->p^d) primes (digits n)


-- copy & paste
primes = 2:(sieve [3, 5 ..])
  where sieve (p:xs) = p: (sieve [ x | x <- xs, x `mod` p /= 0])


digits num  = reverse $ unfoldr f num
  where f a = let (c,d) = divMod a 10
              in  if (c,d) == (0,0) then Nothing
                                    else Just (d,c)

Pythonで. 10000以下の素数の個数桁までは対応.

1
2
3

n = 12345
prime = (x for x in range(2, 10000) if not [i for i in range(2, x) if x % i == 0])
print reduce(lambda p, q : p * prime.next() ** int(q), str(n), 1)

NT系のCMD.EXEでは、SET /Aで計算ができます。

このコード、goedel.batという名で保存してください。バッチファイルが体を張って関数goedelという形態になっているということにさせてください。さすがにバッチファイル内でサブルーチンは無理です……よね？

@ECHO OFF
If NOT "%1"=="/R" (
    CALL %0 /R %1 2 3 5 7 11
    GOTO EXIT
)
SET /A G = 1
SET /A T = %2
:NEXT
    SET /A N = %T:~0,1% + 0
    FOR /L %%I IN (1, 1, %N%) DO SET /A G *= %3
    SET /A T = %T:~1% + 0
    SHIFT
IF NOT "%T%"=="0" GOTO NEXT

ECHO %G%

:EXIT

> バッチファイル内でサブルーチンは無理です... よね?

setlocalとendlocalで変数のスコープを区切り、callと:EOFを組み
合わせればできます。

バッチなので限界はありますが、整数 nの桁数に応じて素数を生成
するようにしました。

素数を生成する部分もサブルーチンにしたかったのですが、戻り値
に複数の値(擬似的な配列)を返すことができなかったので、そこは
あきらめました。

  e.g.
    C:\>@echo off & (for %n in (9 81 230) do #100.bat %n) & echo on
    512
    768
    108

see: Windows 2000コマンドライン徹底活用

@echo off
  setlocal enabledelayedexpansion
    set G=1
    set i=0
    set j=0
    set k=1
    set l=0
    set n=%~1
    set p=
    set t=0
    set v=0
    set x=1
    
    (echo %n%) | findstr /r [0-9] > NUL 2>&1 || (echo usage: %~n0 NUMBER >&2 & exit /b 1)
    
    call :length %n% l
    
    :: 素数を生成
    set p[0]=2
    :LOOP_1
      if %k% geq %l% goto BREAK
      set /a x+=2
      set j=0
      :LOOP_2
        if %j% lss %k% (
          set /a t=x%%!p[%j%]!
          if !t! neq 0 (
            set /a j+=1
            goto LOOP_2
          )
        )
      if %j% equ %k% (
        set p[!k!]=%x%
        set /a k+=1
      )
      goto LOOP_1
    :BREAK
    
    set /a l-=1
    for /l %%i in (0,1,%l%) do (
      call :power !p[%%i]! !n:~%%i,1! v
      set /a G*=v
    )
  endlocal & echo %G%
goto :EOF

:length
  setlocal enabledelayedexpansion
    set i=0
    set t=%~1
    
    if not "%t%" == "" (
      :_
        set t=!t:~1!
        set /a i+=1
      if not "!t!" == "" goto _
    )
  endlocal & set %~2=%i%
goto :EOF

:power
  setlocal
    set n=1
    
    for /l %%i in (1,1,%~2) do set /a n*=%~1
  endlocal & set %~3=%n%
goto :EOF

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - Flatten

Index

Feed

Other

Link

Pathtraq