2015年02月15日

C#で正整数のゲーデル数化

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その70

■問題 (出題者:nobsun さん)
正の整数 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


ゲーデル数とは何かについては、僕はほとんど何も分かってません(^^;;。
でも、定義が明確に書いてあるので、僕にもプログラムが書けますね。
コメントにも書いてありますが、素数を列挙するメソッドは効率無視です。
ここでは、整数 n は、int型としましたので、最大でも、intで表せる桁数分(つまり10個)しか素数を求めないから これで問題ないですね。

戻り値は、BigIntegerにしました。なので、.NET Framework4 以降が対象です。
BigIntegerは、論理上は大きさに上限、下限がないので、int.MaxValueを引数に与えても正しいゲーデル数を返します。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Console.WriteLine(Goedel(9));
            Console.WriteLine(Goedel(81));
            Console.WriteLine(Goedel(230));
            Console.WriteLine(Goedel(4321));
            Console.WriteLine(Goedel(54321));
            Console.WriteLine(Goedel(654321));
            Console.WriteLine(Goedel(7654321));
            Console.WriteLine(Goedel(87654321));
            Console.ReadLine();
        }

        static BigInteger Goedel(int num) {
            BigInteger result = 1;
            string s = num.ToString();
            var ite = GetPrimes().GetEnumerator();
            foreach (var c in s) {
                ite.MoveNext();
                result *= BigInteger.Pow(ite.Current, c - '0');
            }
            return result;
        }
        
        // 素数を列挙する。効率は無視。
        static IEnumerable<int> GetPrimes() {
            for (int i = 2; i < int.MaxValue; i++) {
                bool isPrime = true;
                for (int j = 2; j < i; j++)
                    if (i % j == 0) {
                        isPrime = false;
                        break;
                    }
                if (isPrime)
                    yield return i;
            }
        }
    }
}

MoveNext, Current呼び出してるのは煩雑なので、LInq to Object の Zip メソッド使って Goedel メソッドを書き直してみました。
そうなると、当然ながら、Aggregate 使ったほうが楽ですね。
メソッドチェーンがいい感じです。LINQ最高!
ただ、Aggregateは、慣れるまでは、直感的ではないのが玉に瑕ですね。

        static BigInteger Goedel(int num) {
            var gedel = num.ToString()
                           .Select(c => c - '0')
                           .Zip(GetPrimes(), (d, p) => BigInteger.Pow(p, d))
                           .Aggregate((r, n) => r * n);
            return gedel;
        }
       

以下、結果です。

512
768
108
75600
174636000
5244319080000
2677277333530800000
25968760179275365452000000



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52407162