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

素朴に。

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()

DouKaku?

正整数のゲーデル数化？

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq