Project Euler Problem 918

Solution

Answer: -6999033352333308

Using the recurrences

$$a_{2n}=2a_n,\qquad a_{2n+1}=a_n-3a_{n+1},$$

we derive a recurrence for the partial sums

$$S(N)=\sum_{k=1}^N a_k.$$

For even indices:

$$\begin{aligned} S(2N) &=\sum_{k=1}^N a_{2k}+\sum_{k=0}^{N-1}a_{2k+1}\ &=2S(N)+\left(a_1+\sum_{k=1}^{N-1}(a_k-3a_{k+1})\right)\ &=2S(N)+\left(1+S(N-1)-3(S(N)-1)\right)\ &=4-a_N. \end{aligned}$$

Thus

$$S(10^{12}) = 4-a_{5\cdot 10^{11}}.$$

So it remains to compute $a_{500000000000}$.

A direct memoized recursion is enough because each step halves the argument:

from functools import lru_cache

@lru_cache(None)
def a(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 2 * a(n // 2)
    k = n // 2
    return a(k) - 3 * a(k + 1)

ans = 4 - a(500000000000)
print(ans)

This produces

$$a_{500000000000}=6999033352333312,$$

hence

$$S(10^{12}) = 4-6999033352333312 = -6999033352333308.$$

Answer: -6999033352333308