problem 505 // project euler

Bidirectional Recurrence

Let:
$x(0)=0$
$x(1)=1$
$x(2k)=(3x(k)+2x(lfloor frac k 2 rfloor)) text{ mod } 2^{60} text{ for } k ge 1 text {, where } lfloor text { } rfloor text { is the floor function}$
$x(2k+1)=(2x(k)+3x(lfloor frac k 2 rfloor)) text{ mod } 2^{60} text{ for } k ge 1$
$y_n(k)=x(k) text{ if } k ge n$
$y_n(k)=2^{60} - 1 - max(y_n(2k),y_n(2k+1)) text{ if } k < n$
$A(n)=y_n(1)$

You are given:
$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$

Find $A(10^{12})$.

双向递归

记：
$x(0)=0$
$x(1)=1$
$x(2k)=(3x(k)+2x(lfloor frac k 2 rfloor)) text{ mod } 2^{60} text{ 对于 } k ge 1 text {，其中} lfloor text { } rfloor text {是下取整函数}$
$x(2k+1)=(2x(k)+3x(lfloor frac k 2 rfloor)) text{ mod } 2^{60} text{ 对于 } k ge 1$
$y_n(k)=x(k) text{ if } k ge n$
$y_n(k)=2^{60} - 1 - max(y_n(2k),y_n(2k+1)) text{ if } 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})$。