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