Open Source · 7 Languages · 900+ Problems

Project Euler Solutions

Complete solutions in C++, Python & Java — with step-by-step mathematical explanations

All Problems

Problem 335: Gathering the Beans

Project Euler Problem 335 Solution

EulerSolve provides an optimized solution for Project Euler Problem 335, Gathering the Beans, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Place $n$ bowls in a circle, with one bean in each bowl. Starting from a chosen bowl, Peter removes all beans from the current bowl and drops them one by one into successive bowls clockwise. The next move starts from the bowl that received the last bean. Let $M(n)$ be the number of moves required until the initial all-ones configuration appears again. The problem asks for $\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$ A direct simulation is easy for small $n$, but the upper limit $10^{18}$ makes brute force completely infeasible. The solution therefore isolates a closed form for the special arguments $2^k+1$, then sums that formula as three geometric series. Mathematical Approach State Model and Direct Definition of $M(n)$ Number the bowls $0,1,\dots,n-1$, let $b_i$ be the bean count in bowl $i$, and let $p$ be the current bowl. If the current bowl contains $t=b_p$ beans, one move performs $b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$ The initial state is $(1,1,\dots,1)$. The helper routine simulate_M in the C++ source implements exactly this rule and repeats it until the all-ones state reappears. This gives a literal definition of $M(n)$....

Detailed mathematical approach

Problem Summary

Place $n$ bowls in a circle, with one bean in each bowl. Starting from a chosen bowl, Peter removes all beans from the current bowl and drops them one by one into successive bowls clockwise. The next move starts from the bowl that received the last bean. Let $M(n)$ be the number of moves required until the initial all-ones configuration appears again. The problem asks for

$\sum_{k=0}^{10^{18}} M(2^k+1)\pmod{7^9}.$

A direct simulation is easy for small $n$, but the upper limit $10^{18}$ makes brute force completely infeasible. The solution therefore isolates a closed form for the special arguments $2^k+1$, then sums that formula as three geometric series.

Mathematical Approach

State Model and Direct Definition of $M(n)$

Number the bowls $0,1,\dots,n-1$, let $b_i$ be the bean count in bowl $i$, and let $p$ be the current bowl. If the current bowl contains $t=b_p$ beans, one move performs

$b_p\leftarrow 0,\qquad b_{p+j\pmod n}\leftarrow b_{p+j\pmod n}+1\quad(1\le j\le t),\qquad p\leftarrow p+t\pmod n.$

The initial state is $(1,1,\dots,1)$. The helper routine simulate_M in the C++ source implements exactly this rule and repeats it until the all-ones state reappears. This gives a literal definition of $M(n)$.

The Key Closed Form for $n=2^k+1$

The nontrivial combinatorial ingredient used by the solver is the identity

$\boxed{M(2^k+1)=2^{k+1}+4^k-3^k\qquad(k\ge 0).}$

The code treats this as the central lemma and verifies it against explicit simulation for small $k$. The first values are:

$M(2)=2,\qquad M(3)=5,\qquad M(5)=15,\qquad M(9)=53,$

which match

$2^{1}+4^0-3^0=2,\qquad 2^{2}+4^1-3^1=5,\qquad 2^{3}+4^2-3^2=15,\qquad 2^{4}+4^3-3^3=53.$

The implementation also checks the statement values $M(5)=15$ and $M(100)=10920$ by direct simulation before computing the final answer.

Reducing the Required Sum

Set

$E=10^{18},\qquad S(E)=\sum_{k=0}^{E} M(2^k+1).$

Substituting the closed form and splitting the sum termwise gives

$S(E)=\sum_{k=0}^{E}\left(2^{k+1}+4^k-3^k\right) =\sum_{k=0}^{E}2^{k+1}+\sum_{k=0}^{E}4^k-\sum_{k=0}^{E}3^k.$

So the original process problem is reduced to three standard geometric sums.

Evaluating the Geometric Series

For any ratio $r\neq 1$,

$\sum_{k=0}^{E} r^k=\frac{r^{E+1}-1}{r-1}.$

Applying this identity to the three terms:

$\sum_{k=0}^{E}2^{k+1}=2\sum_{k=0}^{E}2^k=2(2^{E+1}-1),$

$\sum_{k=0}^{E}4^k=\frac{4^{E+1}-1}{3},\qquad \sum_{k=0}^{E}3^k=\frac{3^{E+1}-1}{2}.$

Therefore

$\boxed{S(E)=2(2^{E+1}-1)+\frac{4^{E+1}-1}{3}-\frac{3^{E+1}-1}{2}.}$

This is the exact closed form the code evaluates, with $E=10^{18}$.

Modular Evaluation

The required modulus is

$m=7^9=40{,}353{,}607.$

Because $m$ is odd and not divisible by $3$, both $2$ and $3$ are invertible modulo $m$. Thus the divisions in the geometric-series formula can be replaced by multiplication with modular inverses:

$S(E)\equiv 2(2^{E+1}-1)+(4^{E+1}-1)\cdot 3^{-1}-(3^{E+1}-1)\cdot 2^{-1}\pmod m.$

The only large quantities left are $2^{E+1}$, $3^{E+1}$, and $4^{E+1}$ modulo $m$. These are computed by binary exponentiation, so the huge exponent $10^{18}+1$ is handled in $O(\log E)$ multiplications rather than $O(E)$.

How the Code Works

The C++ file has two clearly separated parts. First, simulate_M and run_validations perform checkpoint verification on small inputs, including the statement values and the formula $M(2^k+1)=2^{k+1}+4^k-3^k$ for $k=0,\dots,8$. Second, solve() computes the modular inverses of $2$ and $3$, evaluates

$2^{E+1}\bmod m,\qquad 3^{E+1}\bmod m,\qquad 4^{E+1}\bmod m,$

forms the three partial sums sum_2, sum_4, and sum_3, and combines them as (sum_2 + sum_4 - sum_3) mod m. The Python version mirrors the same mathematics using pow(base, exp, mod) and Python's built-in modular inverse. The Java version uses the same repeated squaring logic and obtains inverses through BigInteger.modInverse.

Complexity Analysis

The final computation needs only three modular exponentiations and a constant number of modular arithmetic operations, so it runs in $O(\log E)$ time and $O(1)$ memory. Directly simulating the bean process up to $10^{18}$ terms would be hopelessly too slow; simulation appears only in the fixed-size validation phase.