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)。