Project Euler

A Weird Recurrence Relation

Define f on positive integers by: 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) Let S(n) = sum_(i=1)^n f(i). Given S(8) = 22 and S(100) = 3604, find S(3^37) m...

Source sync Apr 19, 2026

Problem #0463

Level Level 13

Solved By 1,306

Languages C++, Python

Answer 808981553

Length 251 words

modular_arithmeticdynamic_programmingrecursion

The function $f$ is defined for all positive integers as follows: $$\begin{cases} 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{cases}$$ The function $S(n)$ is defined as $\sum_{i=1}^{n}f(i)$.

We can verify that $S(8)=22$ and $S(100)=3604$.

Find $S(3^{37})$. Give the last $9$ digits of your answer.

Problem 463: A Weird Recurrence Relation

Mathematical Foundation

Lemma 1 (Dependence on odd part). For all positive integers $n$ , $f(n) = f(\text{odd}(n))$ , where $\text{odd}(n)$ is the largest odd divisor of $n$ .

Proof. Write $n = 2^s \cdot m$ with $m$ odd. By induction on $s$ : if $s = 0$ , $f(n) = f(m)$ trivially. If $s \ge 1$ , $f(n) = f(2 \cdot 2^{s-1} m) = f(2^{s-1} m)$ by the rule $f(2n) = f(n)$ . By the inductive hypothesis, $f(2^{s-1} m) = f(m)$ . $\square$

Theorem 1 (Even-odd splitting). Define $T(k) = \sum_{j=0}^{k} f(2j+1)$ . Then:

S(2N) = S(N) + T(N-1), \qquad S(2N+1) = S(N) + T(N).

Proof. Splitting the sum $S(2N) = \sum_{i=1}^{2N} f(i)$ by parity:

S(2N) = \sum_{i=1}^{N} f(2i) + \sum_{i=1}^{N} f(2i-1) = \sum_{i=1}^{N} f(i) + \sum_{j=0}^{N-1} f(2j+1) = S(N) + T(N-1).

The even-index terms reduce by Lemma 1: $f(2i) = f(i)$ . Adding $f(2N+1)$ gives $S(2N+1) = S(N) + T(N-1) + f(2N+1) = S(N) + T(N)$ . $\square$

Theorem 2 (Recurrence for $T$ ). For $k \ge 2$ :

T(2k) = 2T(k) + 3T(k-1) - S(k) - 2S(k-1) - 1,

T(2k+1) = T(2k) + 3f(2k+1) - 2f(k).

Base cases: $T(0) = 1$ , $T(1) = 4$ .

Proof. Partition the odd numbers $\{1, 3, 5, \ldots, 4k+1\}$ by residue modulo 4. For the $\equiv 1 \pmod{4}$ terms, substitute $f(4j+1) = 2f(2j+1) - f(j)$ ; for the $\equiv 3 \pmod{4}$ terms, substitute $f(4j+3) = 3f(2j+1) - 2f(j)$ . Summing and regrouping in terms of $T$ and $S$ :

\begin{align*} \sum_{j=0}^{k-1} f(4j+1) &= 2\sum_{j=0}^{k-1} f(2j+1) - \sum_{j=0}^{k-1} f(j) = 2(T(k-1) - \text{adjustments}) - (S(k-1) - \text{adjustments}),\\ \sum_{j=0}^{k-1} f(4j+3) &= 3\sum_{j=0}^{k-1} f(2j+1) - 2\sum_{j=0}^{k-1} f(j). \end{align*}

Careful bookkeeping of the boundary term $f(4k+1)$ and combining yields the stated formula. The second equation follows directly: $T(2k+1) = T(2k) + f(4k+3) = T(2k) + 3f(2k+1) - 2f(k)$ . $\square$

Theorem 3 (Complexity). The mutual recursion $(S, T, f)$ with memoization computes $S(n) \bmod 10^9$ in $O(\log^2 n)$ time and $O(\log^2 n)$ space.

Proof. Each recursive call to $S$ , $T$ , or $f$ halves its argument (up to constant offsets). Starting from $n$ , the set of distinct arguments encountered has the form $\{\lfloor n/2^k \rfloor + O(1) : k = 0, 1, \ldots, O(\log n)\}$ . Cross-calls between $S$ , $T$ , and $f$ introduce $O(\log n)$ new arguments per level of recursion, totaling $O(\log^2 n)$ distinct subproblems. Each subproblem requires $O(1)$ arithmetic operations modulo $10^9$ . $\square$

Editorial

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) = sum_{i=1}^{n} f(i). Find S(3^37) mod 10^9. Key insight: S(2N) = S(N) + T(N-1) where T(k) = sum of f at odd indices. With memoization, O(log^2 n) complexity. We else. Finally, else.

Pseudocode

if k is even
else
if n is even
else

Complexity Analysis

Time: $O(\log^2 n)$ distinct subproblems, each requiring $O(1)$ modular arithmetic. For $n = 3^{37} \approx 4.5 \times 10^{17}$ , $\log_2 n \approx 59$ , yielding $\sim 3500$ subproblems.
Space: $O(\log^2 n)$ for the three memoization tables.

Answer

\boxed{808981553}

C++ project_euler/problem_463/solution.cpp

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 463: A Weird Recurrence Relation
 *
 * 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(1) + f(2) + ... + f(n).
 * Compute S(3^37) mod 10^9.
 *
 * Strategy: Mutual recursion S, T, f with memoization.
 *   S(2N)   = S(N) + T(N-1)
 *   S(2N+1) = S(N) + T(N)
 *   T(2k)   = 2T(k) + 3T(k-1) - S(k) - 2S(k-1) - 1
 *   T(2k+1) = T(2k) + 3f(2k+1) - 2f(k)
 *
 * Complexity: O(log^2 n) distinct sub-problems.
 */

const long long MOD = 1000000000LL;

unordered_map<long long, long long> memo_f, memo_S, memo_T;

long long mod(long long x) {
    return ((x % MOD) + MOD) % MOD;
}

long long f_func(long long n);
long long S_func(long long n);
long long T_func(long long k);

long long f_func(long long n) {
    if (n == 1) return 1;
    if (n % 2 == 0) return f_func(n / 2);
    if (memo_f.count(n)) return memo_f[n];

    long long result;
    if (n % 4 == 1) {
        long long k = (n - 1) / 4;
        result = mod(2 * f_func(2 * k + 1) - f_func(k));
    } else { // n % 4 == 3
        long long k = (n - 3) / 4;
        result = mod(3 * f_func(2 * k + 1) - 2 * f_func(k));
    }
    return memo_f[n] = result;
}

long long T_func(long long k) {
    if (k == 0) return 1;
    if (k == 1) return 4;
    if (memo_T.count(k)) return memo_T[k];

    long long result;
    if (k % 2 == 0) {
        long long half = k / 2;
        result = mod(2 * T_func(half) + 3 * T_func(half - 1)
                     - S_func(half) - 2 * S_func(half - 1) - 1);
    } else {
        result = mod(T_func(k - 1) + 3 * f_func(k) - 2 * f_func((k - 1) / 2));
    }
    return memo_T[k] = result;
}

long long S_func(long long n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo_S.count(n)) return memo_S[n];

    long long result;
    if (n % 2 == 0) {
        result = mod(S_func(n / 2) + T_func(n / 2 - 1));
    } else {
        result = mod(S_func(n / 2) + T_func(n / 2));
    }
    return memo_S[n] = result;
}

int main() {
    // Compute 3^37
    long long power = 1;
    for (int i = 0; i < 37; i++) {
        power *= 3;
    }

    // Verify small cases
    assert(S_func(8) == 22 % MOD);
    assert(S_func(100) == 3604 % MOD);

    long long ans = S_func(power);
    cout << ans << endl;

    assert(ans == 808981553LL);

    return 0;
}

Python project_euler/problem_463/solution.py

"""
Problem 463: A Weird Recurrence Relation

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) = sum_{i=1}^{n} f(i). Find S(3^37) mod 10^9.

Key insight: S(2N) = S(N) + T(N-1) where T(k) = sum of f at odd indices.
With memoization, O(log^2 n) complexity.
"""

import sys

sys.setrecursionlimit(10000)

MOD = 10**9

# --- Method 1: Brute force for small n ---
def compute_f_brute(N: int) -> list:
    """Compute f(1..N) directly."""
    f = [0] * (N + 1)
    f[1] = 1
    if N >= 3:
        f[3] = 3
    for n in range(2, N + 1):
        if f[n] != 0:
            continue
        if n % 2 == 0:
            f[n] = f[n // 2]
        elif n % 4 == 1:
            k = (n - 1) // 4
            f[n] = 2 * f[2 * k + 1] - f[k]
        else:  # n % 4 == 3
            k = (n - 3) // 4
            f[n] = 3 * f[2 * k + 1] - 2 * f[k]
    return f

def S_brute(N: int):
    """Compute S(N) by brute force."""
    f = compute_f_brute(N)
    return sum(f[1:N + 1])

# --- Method 2: Memoized recursion for large n ---
class Solver:
    def __init__(self, mod: int):
        self.mod = mod
        self.memo_f = {}
        self.memo_S = {}
        self.memo_T = {}

    def f(self, n: int):
        """Compute f(n) mod self.mod with memoization."""
        if n in self.memo_f:
            return self.memo_f[n]

        if n == 1:
            result = 1
        elif n % 2 == 0:
            result = self.f(n // 2)
        elif n % 4 == 1:
            k = (n - 1) // 4
            result = (2 * self.f(2 * k + 1) - self.f(k)) % self.mod
        else:  # n % 4 == 3
            k = (n - 3) // 4
            result = (3 * self.f(2 * k + 1) - 2 * self.f(k)) % self.mod

        self.memo_f[n] = result
        return result

    def T(self, k: int):
        """Compute T(k) = f(1) + f(3) + ... + f(2k+1) mod self.mod."""
        if k in self.memo_T:
            return self.memo_T[k]

        if k == 0:
            result = 1
        elif k == 1:
            result = 4 % self.mod
        elif k % 2 == 0:
            half = k // 2
            result = (2 * self.T(half) + 3 * self.T(half - 1)
                      - self.S(half) - 2 * self.S(half - 1) - 1) % self.mod
        else:  # k odd
            result = (self.T(k - 1) + 3 * self.f(k) - 2 * self.f((k - 1) // 2)) % self.mod

        self.memo_T[k] = result
        return result

    def S(self, n: int):
        """Compute S(n) = sum_{i=1}^{n} f(i) mod self.mod."""
        if n in self.memo_S:
            return self.memo_S[n]

        if n <= 0:
            return 0
        if n == 1:
            result = 1
        elif n % 2 == 0:
            result = (self.S(n // 2) + self.T(n // 2 - 1)) % self.mod
        else:
            result = (self.S(n // 2) + self.T(n // 2)) % self.mod

        self.memo_S[n] = result
        return result

# --- Verify small cases ---
bf = compute_f_brute(200)
assert S_brute(8) == 22, f"S(8) = {S_brute(8)}"
assert S_brute(100) == 3604, f"S(100) = {S_brute(100)}"

# Verify memoized solver against brute force
solver_check = Solver(10**18)  # large mod to avoid reduction effects
for n in range(1, 100):
    s_bf = S_brute(n)
    s_memo = solver_check.S(n)
    assert s_bf == s_memo, f"S({n}): brute={s_bf}, memo={s_memo}"

# --- Compute the answer ---
solver = Solver(MOD)
ans = solver.S(3**37)
print(ans)
assert ans == 808981553, f"Expected 808981553, got {ans}"