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)。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 206.196.186.174
※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1425319030.A.C48.html
505. Bidirectional Recurrence