Problem 463
A weird recurrence relation
The function f is defined for all positive integers as follows:
- 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)
The function S(n) is defined as ∑i=1nf(i).
S(8)=22 and S(100)=3604.
Find S(337). Give the last 9 digits of your answer.
奇怪的递归关系
定义在全体正整数上的函数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)的定义是∑i=1nf(i)。
已知S(8)=22以及S(100)=3604。
求S(337)并给出其最后9位数字。