0%

Problem 463


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位数字。