Project Euler 197

プロジェクトオイラー
http://projecteuler.net/index.php

Q197.
f (x) = [230.403243784-x2] × 10-9 とする。u0 = -1、un+1 = f (un)としたとき、un + un+1(n = 1012)を求めよ。

値域が狭いので、周期性を調べればよい。xは109倍して整数化すると考えやすいと思う。



from math import pow
from itertools import count

def f(x):
x *= 1e-9
return int(pow(2, a0 - x * x))

N = 10 ** 12
a0 = 30.403243784

u = -1
a = [ u ]
for n in count(1):
u = f(u)
if a.count(u):
break
a.append(u)

period = n - a.index(u)
mod = (N - n) % period
print "%.9f" % ( (a[n+mod-period] + a[n+mod-period+1]) * 1e-9 )