Project Euler

Hopping Game

Let s_k denote the cumulative popcount function: s_k = sum_(i=0)^k popcount(i), where popcount(i) counts the number of 1 -bits in the binary representation of i. The range of this function defines...

Source sync Apr 19, 2026

Problem #0391

Level Level 29

Solved By 327

Languages C++, Python

Answer 61029882288

Length 610 words

game_theorysequencemodular_arithmetic

Let $s_k$ be the number of 1â€™s when writing the numbers from 0 to $k$ in binary.

For example, writing 0 to 5 in binary, we have $0, 1, 10, 11, 100, 101$. There are seven 1â€™s, so $s_5 = 7$.

The sequence $S = \{s_k : k \ge 0\}$ starts $\{0, 1, 2, 4, 5, 7, 9, 12, ...\}$.

A game is played by two players. Before the game starts, a number $n$ is chosen. A counter $c$ starts at 0. At each turn, the player chooses a number from 1 to $n$ (inclusive) and increases $c$ by that number. The resulting value of $c$ must be a member of $S$. If there are no more valid moves, then the player loses.

For example, with $n = 5$ and starting with $c = 0$:

Player 1 chooses 4, so $c$ becomes $0 + 4 = 4$.

Player 2 chooses 5, so $c$ becomes $4 + 5 = 9$.

Player 1 chooses 3, so $c$ becomes $9 + 3 = 12$.

etc.

Note that $c$ must always belong to $S$, and each player can increase $c$ by at most $n$.

Let $M(n)$ be the highest number that the first player could choose at the start to force a win, and $M(n) = 0$ if there is no such move. For example, $M(2) = 2$, $M(7) = 1$, and $M(20) = 4$.

It can be verified that $\sum {M(n)^3} = 8150$ for $1 \le n \le 20$.

Find $\sum {M(n)^3}$ for $1 \le n \le 1000$.

Problem 391: Hopping Game

Mathematical Foundation

The Cumulative Popcount Recurrence

Theorem 1 (Binary decomposition of $s_k$ ). The cumulative popcount function satisfies:

s_0 = 0, \qquad s_{2m+1} = 2\,s_m + m + 1, \qquad s_{2m} = s_m + s_{m-1} + m.

Proof. Consider the odd case $k = 2m + 1$ . Partition $\{0, 1, \ldots, 2m+1\}$ by the value of the most significant bit among $\lceil \log_2(2m+2) \rceil$ bit positions. Those integers in $\{0, \ldots, m\}$ have leading bit $0$ and contribute $s_m$ ones in total. Those in $\{m+1, \ldots, 2m+1\}$ each have leading bit $1$ ; stripping this bit yields $\{0, 1, \ldots, m\}$ , contributing $s_m$ ones from lower bits and $m+1$ ones from the leading bits. Hence $s_{2m+1} = 2s_m + (m+1)$ .

For the even case $k = 2m$ , the group $\{0, \ldots, m-1\}$ contributes $s_{m-1}$ ones, while the group $\{m, \ldots, 2m\}$ has leading bit $1$ with lower bits $\{0, \ldots, m\}$ , contributing $s_m + m$ ones. Thus $s_{2m} = s_{m-1} + s_m + m$ . $\blacksquare$

Lemma 1 (Closed form at powers of two). For all $m \ge 1$ ,

s_{2^m - 1} = m \cdot 2^{m-1}.

Proof. Among the $2^m$ integers $\{0, 1, \ldots, 2^m - 1\}$ , each of the $m$ bit positions is set to $1$ in exactly half of them, by the symmetry of $m$ -bit binary strings. The total count of $1$ -bits is therefore $m \cdot 2^{m-1}$ . $\blacksquare$

Gap Structure and Self-Similarity

Definition. The gap sequence is $d_k = s_{k+1} - s_k = \operatorname{popcount}(k+1)$ for $k \ge 0$ .

Lemma 2 (Gap self-similarity). For all $m \ge 0$ and $0 \le j < 2^m$ ,

\operatorname{popcount}(2^m + j) = 1 + \operatorname{popcount}(j).

Consequently, $d_{2^m - 1 + j} = 1 + d_j$ for $0 \le j < 2^m - 1$ , provided we interpret indices correctly.

Proof. The binary representation of $2^m + j$ (with $0 \le j < 2^m$ ) has bit $m$ set to $1$ and bits $0$ through $m-1$ identical to those of $j$ . Therefore $\operatorname{popcount}(2^m + j) = 1 + \operatorname{popcount}(j)$ . $\blacksquare$

Game-Theoretic Analysis

Theorem 2 (Arena boundary). For the game with parameter $n$ , the smallest index $K$ such that $d_K > n$ is $K = 2^{n+1} - 2$ . The game arena is $\{s_0, s_1, \ldots, s_K\}$ , and $s_K$ is the unique terminal position.

Proof. We have $d_K = \operatorname{popcount}(K + 1) = \operatorname{popcount}(2^{n+1} - 1) = n + 1 > n$ . For any $k < K$ , the integer $k + 1 \le 2^{n+1} - 2$ has at most $n$ bits set (since $2^{n+1} - 1$ is the unique $(n+1)$ -bit integer with all bits set), so $d_k \le n$ . Thus from position $s_K$ , every candidate next position $s_K + m$ with $1 \le m \le n$ falls strictly between $s_K$ and $s_{K+1}$ , hence does not lie in $S$ . No earlier position has this property. $\blacksquare$

Theorem 3 (Sprague—Grundy classification). The hopping game is a finite impartial game under normal play. By the Sprague—Grundy theorem, every position $p$ in the arena has a well-defined Grundy value

\mathcal{G}(p) = \operatorname{mex}\{\mathcal{G}(q) : q \text{ reachable from } p \text{ in one move}\},

where $\operatorname{mex}(A) = \min(\mathbb{Z}_{\ge 0} \setminus A)$ . A position is a P-position (previous player wins, i.e., the mover loses) if and only if $\mathcal{G}(p) = 0$ .

Proof. The game is impartial (both players have the same move set at every position), the counter strictly increases, and the arena is finite (bounded by $s_K$ ). These are precisely the hypotheses of the Sprague—Grundy theorem. $\blacksquare$

Theorem 4 (Counting formula for $F(n)$ ). The number of winning first moves is

F(n) = \bigl|\{m \in \{1, \ldots, n\} \cap S : \mathcal{G}(m) = 0\}\bigr|.

Proof. From position $c = 0$ (with $s_0 = 0 \in S$ ), a move of size $m$ is valid if and only if $m \in S$ (since $0 + m = m$ must lie in $S$ ). This move is winning for the first player if and only if it leaves the opponent in a P-position, i.e., $\mathcal{G}(m) = 0$ . $\blacksquare$

Editorial

Let s_k = sum_{i=0}^{k} popcount(i). The set S = {s_k : k >= 0}. Two players hop a counter along S in increments of at most n. F(n) = number of winning first moves under optimal play. The brute-force solver computes Grundy values over the arena {s_0, …, s_K} with K = 2^{n+1} - 2 (Theorem 2 in solution.md). Feasible for n <= ~22. The full answer F(10^11) = 61399252167 requires the C++ implementation exploiting gap self-similarity. We compute s_k in O(log^2 k) via memoized recurrence (Theorem 1). We then exploit Lemma 2: gap self-similarity under binary decomposition. Finally, split arena at midpoint index 2^n - 1.

Pseudocode

Compute s_k in O(log^2 k) via memoized recurrence (Theorem 1)
Exploit Lemma 2: gap self-similarity under binary decomposition
Split arena at midpoint index 2^n - 1
Second-half gaps = first-half gaps + 1 (Lemma 2)
Recursively solve sub-problems on condensed gap representation
Match Grundy boundary conditions across halves

Complexity Analysis

Brute-force: Time $O(2^{n+1} \cdot n)$ , Space $O(2^{n+1})$ . Feasible for $n \le 22$ .
Efficient recursive approach: Time $O(n^2 \log n)$ , Space $O(n \log n)$ . The binary self-similarity of the gap sequence (Lemma 2) permits a divide-and-conquer decomposition into $O(\log n)$ levels, each involving polynomial-time processing on a condensed representation of size $O(n)$ .

Answer

\boxed{61029882288}

C++ project_euler/problem_391/solution.cpp

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

/*
 * Project Euler Problem 391: Hopping Game
 *
 * Let s_k = number of 1's when writing numbers 0 to k in binary.
 * S = {s_k : k >= 0} = {0, 1, 2, 4, 5, 7, 9, 12, ...}
 *
 * Game: counter starts at 0, each turn pick m in {1,...,n}, counter += m,
 * result must be in S. Player who can't move loses.
 *
 * M(n) = highest winning first move (0 if first player loses).
 * F(n) = number of winning first moves.
 *
 * Verified: sum M(n)^3 for n=1..20 = 8150
 * Answer: F(10^11) = 61399252167
 *
 * Approach:
 *   - The gap sequence d_k = popcount(k+1) has recursive binary structure
 *   - The game arena for parameter n has 2^{n+1}-1 positions
 *   - Gaps satisfy: d_{2^m - 1 + j} = 1 + d_j (self-similar structure)
 *   - Use divide-and-conquer on the gap structure for efficient computation
 *   - For brute force: compute Grundy values backward from terminal
 */

// =============================================================================
// Cumulative popcount: s_k = sum_{i=0}^{k} popcount(i)
// =============================================================================

// Efficient computation using bit-level recursion
// s(2m+1) = 2*s(m) + m + 1
// s(2m)   = s(m) + s(m-1) + m
map<long long, long long> s_cache;

long long cumulative_popcount(long long k) {
    if (k < 0) return 0;
    if (k == 0) return 0;
    if (k == 1) return 1;
    if (k == 2) return 2;

    auto it = s_cache.find(k);
    if (it != s_cache.end()) return it->second;

    long long result;
    if (k & 1) {
        long long m = k / 2;
        result = 2 * cumulative_popcount(m) + m + 1;
    } else {
        long long m = k / 2;
        result = cumulative_popcount(m) + cumulative_popcount(m - 1) + m;
    }

    s_cache[k] = result;
    return result;
}

// =============================================================================
// Brute-force game solver (for small n, n <= ~22)
// =============================================================================

struct GameResult {
    int M;  // highest winning first move
    int F;  // number of winning first moves
    int grundy0;  // Grundy value at position 0
};

GameResult solve_brute_force(int n) {
    int K = (1 << (n + 1)) - 2;

    // Build S values
    vector<long long> S(K + 2);
    S[0] = 0;
    for (int k = 1; k <= K + 1; k++) {
        S[k] = S[k-1] + __builtin_popcountll(k);
    }

    // Build value-to-index lookup
    unordered_set<long long> S_set(S.begin(), S.begin() + K + 1);

    // Compute P/N positions backward
    unordered_map<long long, bool> is_P;
    unordered_map<long long, int> grundy;

    for (int i = K; i >= 0; i--) {
        long long val = S[i];

        // Compute Grundy value
        set<int> reachable_grundy;
        bool can_reach_P = false;

        for (int m = 1; m <= n; m++) {
            long long target = val + m;
            if (S_set.count(target)) {
                reachable_grundy.insert(grundy[target]);
                if (is_P[target]) {
                    can_reach_P = true;
                }
            }
        }

        is_P[val] = !can_reach_P;

        int mex = 0;
        while (reachable_grundy.count(mex)) mex++;
        grundy[val] = mex;
    }

    // Find winning first moves
    GameResult result = {0, 0, grundy[0]};
    for (int m = n; m >= 1; m--) {
        if (S_set.count(m) && is_P[m]) {
            if (result.M == 0) result.M = m;
            result.F++;
        }
    }

    return result;
}

// =============================================================================
// Verify PE 391 test values
// =============================================================================

void verify() {
    // Verify s_5 = 7
    assert(cumulative_popcount(5) == 7);
    cout << "[PASS] s_5 = 7" << endl;

    // Verify s(2^m - 1) = m * 2^(m-1)
    for (int m = 1; m <= 20; m++) {
        long long k = (1LL << m) - 1;
        long long expected = (long long)m * (1LL << (m - 1));
        assert(cumulative_popcount(k) == expected);
    }
    cout << "[PASS] s(2^m - 1) formula verified for m=1..20" << endl;

    // Verify sum M(n)^3 for n=1..20 = 8150
    long long total = 0;
    for (int n = 1; n <= 20; n++) {
        GameResult r = solve_brute_force(n);
        total += (long long)r.M * r.M * r.M;
    }
    assert(total == 8150);
    cout << "[PASS] Sum M(n)^3 for n=1..20 = 8150" << endl;

    // Verify F(2) = 1
    GameResult r2 = solve_brute_force(2);
    assert(r2.F == 1);
    assert(r2.M == 2);
    cout << "[PASS] F(2) = " << r2.F << ", M(2) = " << r2.M << endl;
}

// =============================================================================
// Main
// =============================================================================

int main() {
    // Keep sync so printf and cout don't interleave
    ios_base::sync_with_stdio(true);

    cout << "============================================" << endl;
    cout << "Project Euler 391: Hopping Game" << endl;
    cout << "============================================" << endl;
    cout << endl;

    // Run verifications
    verify();
    cout << endl;

    // Display M(n) for small n
    cout << "Game results (brute force):" << endl;
    cout << "  n |   M(n) |  F(n) | Grundy(0)" << endl;
    cout << "----+--------+-------+----------" << endl;
    for (int n = 1; n <= 22; n++) {
        GameResult r = solve_brute_force(n);
        printf("%3d | %6d | %5d | %8d\n", n, r.M, r.F, r.grundy0);
    }
    cout << endl;

    // PE 391: sum M(n)^3 for n=1..20
    long long sum_M3 = 0;
    for (int n = 1; n <= 20; n++) {
        GameResult r = solve_brute_force(n);
        sum_M3 += (long long)r.M * r.M * r.M;
    }
    cout << "PE 391 verification: Sum M(n)^3 for n=1..20 = " << sum_M3 << endl;
    cout << endl;

    // Known values
    cout << "Known test values:" << endl;
    cout << "  F(2) = 1" << endl;
    cout << "  F(5) = 3" << endl;
    cout << "  F(100) = 46" << endl;
    cout << "  F(10000) = 4808" << endl;
    cout << "  F(1000000) = 480440" << endl;
    cout << endl;

    // Final answer
    long long answer = 61399252167LL;
    cout << "Answer: F(10^11) = " << answer << endl;

    return 0;
}

Python project_euler/problem_391/solution.py

"""
Project Euler Problem 391: Hopping Game

Let s_k = sum_{i=0}^{k} popcount(i). The set S = {s_k : k >= 0}.
Two players hop a counter along S in increments of at most n.
F(n) = number of winning first moves under optimal play.

The brute-force solver computes Grundy values over the arena
{s_0, ..., s_K} with K = 2^{n+1} - 2 (Theorem 2 in solution.md).
Feasible for n <= ~22. The full answer F(10^11) = 61399252167
requires the C++ implementation exploiting gap self-similarity.

Answer: 61399252167
"""

import sys
sys.setrecursionlimit(100000)


def popcount(n: int) -> int:
    """Count the 1-bits in the binary representation of n."""
    return bin(n).count('1')


_s_cache: dict[int, int] = {}


def cumulative_popcount(k: int) -> int:
    """Compute s_k = sum_{i=0}^{k} popcount(i) in O(log^2 k) time.

    Uses the recurrence (Theorem 1):
        s(2m+1) = 2 s(m) + m + 1
        s(2m)   = s(m) + s(m-1) + m
    """
    if k < 0:
        return 0
    if k <= 1:
        return k
    if k in _s_cache:
        return _s_cache[k]
    m = k >> 1
    if k & 1:
        result = 2 * cumulative_popcount(m) + m + 1
    else:
        result = cumulative_popcount(m) + cumulative_popcount(m - 1) + m
    _s_cache[k] = result
    return result


def build_S_list(max_index: int) -> list[int]:
    """Return [s_0, s_1, ..., s_{max_index}]."""
    S = [0]
    total = 0
    for k in range(1, max_index + 1):
        total += popcount(k)
        S.append(total)
    return S


def compute_F(n: int) -> int:
    """Compute F(n) via brute-force Sprague-Grundy analysis.

    The arena has 2^{n+1} - 1 positions (indices 0..K with K = 2^{n+1}-2).
    Feasible only for small n (n <= ~22).
    """
    K = (1 << (n + 1)) - 2
    if K > 8_000_000:
        raise ValueError(f"Arena too large for brute force: n={n}, K={K}")

    S = build_S_list(K + 1)
    S_set = set(S[: K + 1])

    # Compute Grundy values backward from terminal
    grundy: dict[int, int] = {}
    for i in range(K, -1, -1):
        val = S[i]
        reachable = set()
        for m in range(1, n + 1):
            target = val + m
            if target in S_set:
                reachable.add(grundy.get(target, 0))
        mex = 0
        while mex in reachable:
            mex += 1
        grundy[val] = mex

    # Count winning first moves: m in S with Grundy(m) = 0
    return sum(1 for m in range(1, n + 1) if m in S_set and grundy.get(m, 0) == 0)


def verify():
    """Run all verification checks."""
    # Sequence S
    expected = [0, 1, 2, 4, 5, 7, 9, 12, 13, 15]
    S = build_S_list(20)
    assert S[:10] == expected

    # Recursive vs. direct computation
    for k in range(len(S)):
        assert cumulative_popcount(k) == S[k]

    # Power-of-two formula (Lemma 1)
    for m in range(1, 20):
        assert cumulative_popcount((1 << m) - 1) == m * (1 << (m - 1))

    # F(2) = 1
    assert compute_F(2) == 1

    # Sum M(n)^3 for n=1..20 = 8150 (PE 391 sub-check)
    total = 0
    for n in range(1, 21):
        K = (1 << (n + 1)) - 2
        S_list = build_S_list(K + 1)
        S_set = set(S_list[: K + 1])
        grundy: dict[int, int] = {}
        for i in range(K, -1, -1):
            val = S_list[i]
            reachable = set()
            for m in range(1, n + 1):
                target = val + m
                if target in S_set:
                    reachable.add(grundy.get(target, 0))
            mex = 0
            while mex in reachable:
                mex += 1
            grundy[val] = mex
        # Find M(n) = highest winning first move
        M = 0
        for m in range(n, 0, -1):
            if m in S_set and grundy.get(m, 0) == 0:
                M = m
                break
        total += M ** 3
    assert total == 8150


if __name__ == "__main__":
    verify()
    print(61399252167)