Meertens数
Posted feedbacks - Ruby
Intel(R) Xeon(TM) CPU 3.00GHzで10進10桁まで 探索して約40640秒(11時間くらい)でした. 単純計算で20桁では1288年間くらいの計算時間 になります. ゲーデル数算出時, 元の整数を超えたら計算を打 ち切っていますが, この打ち切りの有無も含めて各 桁数までの計算時間 (秒数)は以下のようになりま す. 桁: 打ち切り無, 打ち切り有 1: 1.1e-4, 7.6e-5 2: 2.5e-4, 2.3e-4 3: 1.5e-3, 1.6e-3 4: 1.7e-2, 1.5e-2 5: 0.20, 0.16 6: 2.3, 1.7 7: 25, 19 10: - ,4.1e+4
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 | require "mathn"
N=10
def meertens(n)
prime = Prime.new
primes = Array.new(n+1){prime.next}
prime_list = primes.collect{|i| Array.new(10){|j| i**j}}
result = Array.new
goedel = 1
n.times{|d|
s = 10**d
e = s*10 - 1
s.upto(e){|i|
if i%10 == 0
k = 0
goedel = 1
i.to_s.each_byte{|j|
goedel *= prime_list[k][j-48]
break if goedel > i
k += 1
}
else
next if goedel > i
goedel *= primes[d]
end
result << i if goedel == i
}
}
puts result
end
meertens(N)
|
nobsun
#4710()
Rating4/4=1.00
お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．
このような数のことをMeertens数と言うそうです．
32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．
1 reply [ reply ]