Meertens数
Posted feedbacks - Python
とりあえず、再帰で書いてみた。 searchMeertens(n)でn桁の範囲で探索します。 8桁で一つ見つかりました。 8桁を調べるのに160秒かかりました。 桁数が上がるごとに10倍の計算量になるので、 10桁では4時間くらいかなぁ。 とりあえず、累乗計算をしないようにしたけど、これからどうしようかな。 もうちょっと枝が刈れそうな気がするけど。 Cで書けばもうちょっと早くなるかな。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | import time
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 searchMeertens(keta):
def _search(keta,count,r,n,primes,first):
n *= 10
for x in range(first,10):
if x:
r *= primes[count]
n += 1
if r == n:
print "Found Meertens.",n
if keta > 1:
_search(keta - 1, count + 1, r ,n ,primes, 0)
p = CreatePrimes(20)
_search(keta,0,1,0,p,1)
keta = 10
t0 = time.time()
t1 = t0
for n in range(1,keta+1):
searchMeertens(n)
print n , time.time() - t1 , "sec"
t1 = time.time()
print "total time", time.time() - t0
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]