ProjectEuler 505 Bidirectional Recurre - 拼圖

505. Bidirectional Recurrence

https://projecteuler.net/problem=505

令：

x(0) = 0

x(1) = 1

x(2k) = 3x(k) + 2x([k/2]) mod 2^60 對所有k≧1，其中[]是高斯函數

x(2k+1) = 2x(k) + 3x([k/2]) mod 2^60 對所有k≧1

y_n(k) = x(k) 若k≧n
2^60 - 1 - max(y_n(2k),y_n(2k+1)) 若k<n

A(n) = y_n(1)

已知：

x(2) = 3

x(3) = 2

x(4) = 11

y_4(4) = 11

y_4(3) = 2^60 - 9

y_4(2) = 2^60 - 12

y_4(1) = A(4) = 8

A(10) = 2^60 - 34

A(10^3) = 101881

請求出A(10^12)。

--