ProjectEuler 463 A weird recurrence re - 拼圖

463. A weird recurrence relation

http://projecteuler.net/problem=463

一函數f對所有正整數定義如下：

　‧f(1) = 1
　‧f(3) = 3
　‧f(2n) = f(n)
　‧f(4n+1) = 2f(2n+1) - f(n)
　‧f(4n+3) = 3f(2n+1) - 2f(n)

定義函數S(n)為Σf(i)對1≦i≦n的和。

S(8) = 22以及S(100) = 3604。

請求出S(3^37)，並給出結果的末九位數作為答案。

--