Project Euler Problem 463
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) -
Solution
Answer: 808981553
We are given the recursively-defined function
$$\begin{aligned} 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), \end{aligned}$$
and
$$S(n)=\sum_{i=1}^n f(i).$$
We must compute
$$S(3^{37}) \pmod{10^9}.$$
1. Mathematical analysis
Step 1: Understanding the structure of $f(n)$
The recursion reduces arguments roughly by factors of $2$ or $4$, so memoized recursion will be efficient even for $3^{37}$.
Let
$$a_n=f(2n+1)$$
(the odd-indexed values).
From the defining relations:
$$\begin{aligned} a_{2n} &=f(4n+1) =2f(2n+1)-f(n) =2a_n-f(n), \[1ex] a_{2n+1} &=f(4n+3) =3f(2n+1)-2f(n) =3a_n-2f(n). \end{aligned}$$
These identities allow us to derive recurrences for $S(n)$.
Step 2: Deriving recurrences for $S(n)$
We split numbers by residue class modulo $4$.
After algebraic manipulation (using the relations above and the identity $f(2n)=f(n)$), one obtains:
$$\boxed{ S(4n) = 6S(2n)-8S(n)+3f(n)-1 }$$
$$\boxed{ S(4n+1) = 6S(2n)-8S(n)+2f(n)+2f(2n+1)-1 }$$
$$\boxed{ S(4n+2) = 6S(2n)-8S(n)+2f(n)+3f(2n+1)-1 }$$
$$\boxed{ S(4n+3) = 6S(2n)-8S(n)+6f(2n+1)-1 }$$
These formulas reduce the problem size from $n$ to roughly $n/2$, giving logarithmic complexity.
Step 3: Complexity
For $N=3^{37}$,
$$3^{37}\approx 4.5\times 10^{17},$$
but every recursive call divides the argument by $2$ or $4$, so memoization makes the computation extremely fast.
We only need the last $9$ digits, so all arithmetic can be performed modulo
$$10^9.$$
2. Python implementation
from functools import lru_cache
MOD = 10**9
# -------------------------------------------------------
# f(n)
# -------------------------------------------------------
@lru_cache(None)
def f(n):
if n == 1:
return 1
if n == 3:
return 3
# even case
if n % 2 == 0:
return f(n // 2)
# n = 4k + 1
if n % 4 == 1:
k = (n - 1) // 4
return 2 * f(2 * k + 1) - f(k)
# n = 4k + 3
k = (n - 3) // 4
return 3 * f(2 * k + 1) - 2 * f(k)
# -------------------------------------------------------
# Small exact values for S(n)
# -------------------------------------------------------
small = [0]
s = 0
for i in range(1, 20):
s += f(i)
small.append(s)
# -------------------------------------------------------
# S(n)
# -------------------------------------------------------
@lru_cache(None)
def S(n):
if n < 20:
return small[n]
q, r = divmod(n, 4)
if r == 0:
ans = (
6 * S(2 * q)
- 8 * S(q)
+ 3 * f(q)
- 1
)
elif r == 1:
ans = (
6 * S(2 * q)
- 8 * S(q)
+ 2 * f(q)
+ 2 * f(2 * q + 1)
- 1
)
elif r == 2:
ans = (
6 * S(2 * q)
- 8 * S(q)
+ 2 * f(q)
+ 3 * f(2 * q + 1)
- 1
)
else: # r == 3
ans = (
6 * S(2 * q)
- 8 * S(q)
+ 6 * f(2 * q + 1)
- 1
)
return ans
# -------------------------------------------------------
# Required value
# -------------------------------------------------------
N = 3**37
print(S(N) % MOD)
3. Code walkthrough
Function f(n)
The recursive definition is implemented directly.
- If $n$ is even:
$$f(2n)=f(n)$$
- If $n=4k+1$:
$$f(4k+1)=2f(2k+1)-f(k)$$
- If $n=4k+3$:
$$f(4k+3)=3f(2k+1)-2f(k)$$
Memoization (@lru_cache) ensures every value is computed once.
Function S(n)
Uses the derived recurrences for each residue modulo $4$.
Example:
If $n=4q+2$,
6 * S(2*q)
- 8 * S(q)
+ 2 * f(q)
+ 3 * f(2*q + 1)
- 1
This reduces the problem to much smaller arguments.
Verification on the given examples
The program reproduces:
$$S(8)=22$$
and
$$S(100)=3604.$$
So the recurrence system is consistent with the problem statement.
4. Final verification
The recursion depth is only $O(\log n)$, so evaluating $S(3^{37})$ is computationally trivial with memoization.
The computed value modulo $10^9$ is:
$$808981553.$$
Therefore the last $9$ digits are:
Answer: 808981553