Problem 169

http://projecteuler.net/index.php?section=problems&id=169

2の累乗が出てきたら、2進数で考えたくなるのが人情。

少し観察すると、2が伝播していく、感じ。つまり、最後が2か、そうでないかで状況が変わる。

でいろいろやった結果、最終的に次のように考えた。

nを1/2までつかって表現する。

その結果を使って2*n,2*n+1を1/2まで使って表現してみる。

これを逆向きに行う。

f 1 = (1,1)
f n | even n = (z+t,t)
| otherwise = (z,z+t)
where (z,t) = f $ n `div` 2
p169 = fst.f $ 10^25
More Reading
Newer// 最近
Older// Problem 167