Problem 334: Spilling the Beans

Project Euler Problem 334 Solution

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

Problem Summary The bowls start with a deterministic pseudo-random number of beans. A legal move chooses a bowl containing at least two beans, removes two beans from it, and places one bean in each neighboring bowl. The task is to count how many such spills occur before every bowl contains at most one bean. Mathematical Approach Index the bowls by integers and let $b_i$ be the number of beans in bowl $i$. Although the input generator only produces finitely many nonzero bowls, the process is best viewed on the whole integer line, because beans may move left of the original range. State Variables and Invariants The code tracks three global quantities: $$B=\sum_i b_i,\qquad M_1=\sum_i i\,b_i,\qquad M_2=\sum_i i^2 b_i.$$ Here $B$ is the total number of beans, $M_1$ is the first moment, and $M_2$ is the second moment. One spill at position $i$ changes the state by $$b_i\mapsto b_i-2,\qquad b_{i-1}\mapsto b_{i-1}+1,\qquad b_{i+1}\mapsto b_{i+1}+1.$$ The bean count is preserved because $-2+1+1=0$. The first moment is also preserved because $$(-2)\,i + (i-1) + (i+1) = 0.$$ Therefore every reachable configuration has the same values of $B$ and $M_1$ as the initial one....

Detailed mathematical approach

Problem Summary

Infinitely many bowls stand in a straight line with finitely many beans spread over them. Only one move is allowed: take two beans out of one bowl and put one of them into each neighbouring bowl. The game is over as soon as every bowl holds one bean or none. The statement shows two adjacent bowls with $2$ and $3$ beans, which take eight moves to finish. The starting heaps come from $t_0=123456$, with $t_{i-1}$ halved when it is even and replaced by $\lfloor t_{i-1}/2\rfloor\oplus 926252$ when it is odd, $\oplus$ being bitwise exclusive or, ^[6] and $b_i=(t_i\bmod 2^{11})+1$. The statement gives $b_1=289$, $b_2=145$ and $3419100$ moves for those two heaps in adjacent bowls. We must find the number of moves for $1500$ adjacent bowls holding $b_1,\ldots,b_{1500}$ beans, every other bowl empty. ^[1]

The whole solution in one sentence: a move changes neither the number of beans nor their centre of mass but always raises $\sum i^2b_i$ by exactly $2$, and when the occupied bowls form an unbroken block, as they do here, the game comes to rest in the one finished position with the right bean count and centre of mass whose $\sum i^2$ is smallest — so the move count is half the difference of two such sums.

Mathematical Approach

1. The board and the move

Number the bowls by all integers and let $b_i$ be the number of beans in bowl $i$, with only finitely many $b_i$ nonzero. Call a bowl loud when it holds at least two beans and quiet otherwise. A move at a loud bowl $i$ replaces

$$b_i\mapsto b_i-2,\quad b_{i\pm1}\mapsto b_{i\pm1}+1.$$

Two things make the game harder than it looks. Beans leave the range they started in: in the statement's example the heaps sit in bowls $0$ and $1$, yet the game ends with beans in bowls $-2,-1,1,2,3$. And a quiet bowl can be refilled by its neighbours, so no single left-to-right sweep finishes the job. The $1500$ given bowls are numbered $0$ to $1499$ below, as the programs number them; shifting all indices changes nothing, since it permutes the moves one to one.

2. Three running sums

Keep track of three quantities, the bean count and the first two moments of the bean positions: ^[2]

$$B=\sum_i b_i,\quad M_1=\sum_i i\,b_i,\quad M_2=\sum_i i^2b_i.$$

A single move at bowl $i$ removes two beans from position $i$ and creates one at $i-1$ and one at $i+1$, so each sum changes by the same expression evaluated on the weights $-2,+1,+1$:

bean count: $-2+1+1=0$;
first moment: $-2i+(i-1)+(i+1)=0$;
second moment: $-2i^2+(i-1)^2+(i+1)^2=2$.

The first two cancel for every $i$, so $B$ and $M_1$ never change. In the third the cross terms $\pm2i$ cancel and the squares $(\pm1)^2$ remain, leaving a constant $2$ that is also independent of $i$.

3. The move count is decided by the finishing position alone

Write $M_2$ from here on for the second moment of the starting position. After $m$ moves the second moment is $M_2+2m$, whatever the moves were, so a play that finishes at a position of second moment $M_2^{\ast}$ has length

$$m=\tfrac12\bigl(M_2^{\ast}-M_2\bigr).$$

For the two bowls with $2$ and $3$ beans, $B=5$, $M_1=3$ and $M_2=3$. Playing always at the leftmost loud bowl gives the eight moves at bowls $0,1,1,0,-1,2,1,0$, with the second moment running through $3,5,7,\ldots,19$, and indeed $(19-3)/2=8$. The task is therefore to decide which position the game ends in.

A free check comes with it: since $i^2$ and $i$ have the same parity, $M_2\equiv M_1\pmod 2$ for every position, so two positions with the same first moment have second moments of equal parity and the difference above is always even.

4. What a finished position looks like

A finished position has no loud bowl, so every $b_i\in\{0,1\}$: it is a set of $B$ distinct integers. By Section 2 that set has sum $M_1$. For the example, a finished position is a set of five distinct integers with sum $3$, and the game reached $\{-2,-1,1,2,3\}$, whose squares add up to $19$.

5. The cheapest finished position

Among all sets of $B$ distinct integers with sum $M$ there is exactly one whose sum of squares is smallest. Write

$$T=M-\frac{B(B-1)}{2}=qB+r,\quad 0\le r\lt B,$$

with $q=\lfloor T/B\rfloor$. The minimiser is the block of $B+1$ consecutive bowls from $q$ to $q+B$ with the single bowl $q+B-r$ left out:

$$\{q,q+1,\ldots,q+B\}\setminus\{q+B-r\}.$$

For $r=0$ the omitted bowl is the right end and the set is the plain block $q,\ldots,q+B-1$.

Proof. Only finitely many such sets have a sum of squares below any given bound, so a minimiser exists. Write it as $x_0\lt x_1\lt\cdots\lt x_{B-1}$ and put $y_j=x_j-j$; strict increase of the $x_j$ is the same as $y_0\le\cdots\le y_{B-1}$, and $\sum_j y_j=T$. Suppose $y_{B-1}\ge y_0+2$, let $a$ be the largest index with $y_a=y_0$ and $b$ the smallest with $y_b=y_{B-1}$, so $a\lt b$, and raise $y_a$ by $1$ while lowering $y_b$ by $1$. The sequence stays non-decreasing, because $y_{a+1}\ge y_a+1$ and $y_{b-1}\le y_b-1$ by the choice of $a$ and $b$, and $y_a+1\le y_b-1$ when $b=a+1$. The sum is unchanged, while the sum of squares changes by

$$(x_a+1)^2-x_a^2+(x_b-1)^2-x_b^2=2(x_a-x_b+1).$$

Here $x_b-x_a=(b-a)+(y_b-y_a)$${}\ge1+2=3$, so the change is at most $-4$, contradicting minimality. Hence $y_{B-1}\le y_0+1$: the $y_j$ take only the values $q$ and $q+1$, the smaller first, and their sum forces exactly $r$ of them to be $q+1$. That pins the set down uniquely, and $x_j=y_j+j$ gives the block above. $\square$

For $B=5$ and $M=3$ this gives $T=3-10=-7=(-2)\cdot5+3$, so $q=-2$, $r=3$ and the set is $\{-2,\ldots,3\}$ without bowl $q+B-r=0$, that is $\{-2,-1,1,2,3\}$ with sum of squares $19$ — exactly where the example game stopped. The runner-up $\{-3,0,1,2,3\}$ reaches $23$: same sum, but two empty bowls inside its range instead of one.

6. No bowl can fire more often than a stabilising count allows

It remains to show that the game really reaches the cheapest position. Say that bowl $i$ fires when a move is made at it and let $f_i$ count its firings so far. Each firing of $i$ costs it two beans and each firing of a neighbour brings one, so the content of bowl $i$ is always $b_i-2f_i+f_{i-1}+f_{i+1}$. Now put $c_i=1$ when bowl $i$ belongs to the cheapest position of Section 5 and $c_i=0$ otherwise, and suppose we have non-negative integers $u_i$, all but finitely many zero, such that for every bowl $i$

$$b_i-2u_i+u_{i-1}+u_{i+1}=c_i.$$

Lemma. In every legal play, $f_i\le u_i$ for every bowl at every instant.

Proof. Otherwise look at the first move that breaks it, say at bowl $i$. Just before that move $f_j\le u_j$ for all $j$ and $f_i=u_i$, so the content of bowl $i$ is

$$\begin{aligned}b_i-2u_i+f_{i-1}+f_{i+1}&\le b_i-2u_i+u_{i-1}+u_{i+1}\\&=c_i\le1,\end{aligned}$$

and a bowl with at most one bean cannot fire. $\square$

Three conclusions follow. Every play stops, after at most $\sum_i u_i$ moves. Summing $i^2$ against the displayed equation gives $\sum_i i^2(c_i-b_i)=2\sum_i u_i$, as in Section 2, so $\sum_i u_i=\tfrac12(M_2(c)-M_2)$. And a stopped play sits in a finished position with $M_2^{\ast}\ge M_2(c)$ by Section 5, so by Section 3 its length is

$$m=\tfrac12\bigl(M_2^{\ast}-M_2\bigr)\ge\sum_i u_i\ge m.$$

Equality throughout forces $M_2^{\ast}=M_2(c)$, and since the cheapest position is unique, the game ends exactly at $c$ and fires bowl $i$ exactly $u_i$ times. This is the order-independence of chip-firing and sandpile models together with the least action principle: the firing counts of a real play are the smallest that reach rest. ^[2] ^[3] ^[4]

7. When the firing counts come out non-negative

Only the existence of such $u_i\ge0$ is still open. Put $v_i=c_i-b_i$; by Section 2 and the definition of $c$, $\sum_i v_i=0$ and $\sum_i i\,v_i=0$, which is just what is needed to solve the equation of Section 6 by summing twice:

$$u_i=\sum_{j\lt i}(i-j)\,v_j,\qquad S_k=\sum_{j\le k}v_j,$$

so that $u_i=\sum_{k\lt i}S_k$. Differencing twice returns the equation of Section 6,

$$u_{i+1}-u_i=S_i,\qquad u_{i-1}-2u_i+u_{i+1}=v_i,$$

and $u_i$ vanishes at both ends: far to the left the sum is empty, far to the right it equals $i\sum_j v_j-\sum_j jv_j=0$. It is the only finitely supported solution: the difference of two would have vanishing second differences, hence constant first differences, which vanish far out and so everywhere. For the heaps $2$ and $3$ the counts are $u_{-1}=u_2=1$ and $u_0=u_1=3$, eight firings in all.

Suppose now the bowls holding beans form a block of consecutive bowls, say $0$ to $n-1$, with no empty bowl inside. Outside the block $v_i=c_i\ge0$, inside it $v_i=c_i-b_i\le1-1=0$. So $S_k$ rises from $0$ up to $k=-1$, falls across the block and rises back to $0$: non-negative left of the block, non-positive from its right end on, so its nonzero values change sign at most once, from positive to negative. Then $u_i=\sum_{k\lt i}S_k$ rises, then falls, and is $0$ at both ends, so $u_i\ge0$ everywhere. Every $b_i=(t_i\bmod2^{11})+1$ is at least $1$, so the $1500$ given bowls are such a block and the method applies.

8. A pitfall: beans that are too far apart

That hypothesis is not decoration. One bean in bowl $0$ and one in bowl $3$ is a finished position already, so the answer is $0$ moves and its sum of squares is $9$; but $B=2$ and $M=3$ give $q=1$, $r=0$ and the cheapest set $\{1,2\}$ with $5$, so subtracting and halving would report $-2$ moves. Likewise two beans in bowl $0$ and one in bowl $100$: one move finishes at $\{-1,1,100\}$ with $10002$, while the cheapest set $\{32,33,35\}$ has $3338$, which would give $-3331$. The beans are too far apart to merge into one block, the counts of Section 7 come out negative, and the cheapest position is not reachable.

9. Worked example: the two bowls of the statement

Put $b_1=289$ beans in bowl $0$ and $b_2=145$ in bowl $1$. Then $B=434$, $M_1=145$ and $M_2=145$. With $B(B-1)/2=93961$,

$$T=145-93961=-93816=(-217)\cdot434+362,$$

so $q=-217$, $r=362$ and $B-r=72$. The game must end on bowls $-217$ to $217$ with bowl $-217+72=-145$ empty. Its second moment is

$$\begin{aligned}\sum_{x=-217}^{217}x^2&=\frac{2\cdot217\cdot218\cdot435}{6}\\&=6859370\end{aligned}$$

minus $145^2=21025$, that is $6838345$, and

$$\tfrac12(6838345-145)=3419100,$$

the number quoted in the statement. A bean-by-bean simulation of all $434$ beans confirms both the count and the finishing position.

10. The second moment of the final block in closed form

The final block has over a million members and must never be listed bowl by bowl. It is two runs of consecutive bowls, of lengths $n_1=B-r$ from $q$ and $n_2=r$ from $q+n_1+1$, and for a run the sum of squares is

$$\begin{aligned}\sum_{k=0}^{n-1}(a+k)^2&=na^2+an(n-1)\\&\quad+\frac{n(n-1)(2n-1)}{6},\end{aligned}$$

from $\sum_{k=0}^{n-1}k=n(n-1)/2$ and $\sum_{k=0}^{n-1}k^2=n(n-1)(2n-1)/6$, the second being a square pyramidal number. ^[5] Two evaluations of this expression give $M_2(c)$ in constant time.

11. The instance with 1500 bowls

The generator starts $b_1,\ldots,b_6$ as $289,145,1097,1573,1811,1930$; over the $1500$ bowls the heaps run from $2$ to $2047$ and add up to $B=1533708$ beans, about $1022.47$ per bowl on average. The centre of mass $M_1/B$ is about $759.35$, near the middle of the row, and the final block occupies bowls $-766095$ to $767613$ with its one empty bowl at $-537261$: $228834$ occupied bowls before the hole and $1304874$ after it, three quarters of a million bowls past each end of the original row.

The move count is of the order of $10^{17}$, so even at a billion moves per second a bean-by-bean simulation would run for about five years. The two run sums replace that work by evaluating the rise of the second moment directly.

12. A single bowl, as an extra check

Put $n\ge1$ beans in bowl $0$ and leave the rest empty; then $M_1=M_2=0$ and $T=-n(n-1)/2$. For odd $n$ this gives $q=-(n-1)/2$ and $r=0$, a block symmetric about bowl $0$; for even $n$, $q=-n/2$ and $r=n/2$, the symmetric block of $n+1$ bowls with the middle one empty. Either way the final second moment is $2P(\lfloor n/2\rfloor)$, where

$$P(m)=\frac{m(m+1)(2m+1)}{6},$$

so the game takes $P(\lfloor n/2\rfloor)$ moves: $0,1,1,5,5,14,14,30,30,55$ for $n=1,\ldots,10$, the square pyramidal numbers each taken twice. ^[5]

How the Code Works

Each program first builds the heaps from the recurrence: C++ in generate_beans(count), keeping $t$ in a std::uint64_t; Python in a list of unbounded integers; Java in generateBeans(count) with a signed long and an ArrayList of Long. All three test the low bit for parity, halve by integer division, apply ^ 926252 in the odd case and keep the lowest $11$ bits before adding $1$. The update comes before the value is stored, so the first element is $b_1$, not $b_0$. No fixed width can overflow: $t$ starts below $2^{20}$, halving keeps it there, and $926252\lt2^{20}$, so the exclusive or sets no higher bit.

Sections 2, 5 and 10 then follow inside moves_needed(beans) in C++ and Python, and directly inside solve() in Java, which has no such function. One pass over the heaps, indexed from $0$, accumulates $B$, $M_1$ and $M_2$ into total, first_moment and second_moment, named firstMoment and secondMoment in Java. Each version forms target_shift $=M_1-B(B-1)/2$, the quantity $T$ of Section 5, splits it into q and r, sets n1 $=B-r$ and n2 $=r$, and adds the two runs of Section 10 through sum_squares_arith(first, n), sumSquaresArith in Java. The result is the difference of the two second moments divided by two.

The split of $T$ needs care with each language's integer division, because $T$ is negative here. C++ truncates integer division towards zero and gives a remainder with the sign of the dividend, ^[7] so a plain / would return $-766094$ instead of $-766095$ and leave $r$ negative, breaking $0\le r\lt B$. The helper floor_div therefore subtracts one when the remainder is negative, and r is recovered as target_shift - q * B rather than with %. Python needs no helper, since // already rounds towards minus infinity. ^[7] Java truncates like C++, so the port carries properFloorDiv and properFloorMod; beside them sits an unused floorDiv that merely calls divide, dead code worth recognising as such.

Integer width is the other difference. The widest intermediate value is $n_2(n_2-1)(2n_2-1)$, about $4.44\cdot10^{18}$, below $2^{63}-1\approx9.22\cdot10^{18}$ by less than a factor of three; the second moments reach about $3.0\cdot10^{17}$. The C++ keeps every accumulator in the 128-bit extension types __int128 and unsigned __int128 ^[8] and prints the result with to_string_u128, a decimal conversion by repeated division, as those types have no stream output. Python uses unbounded integers and Java BigInteger. ^[8]

run_checkpoints in the C++ version checks the three facts the statement supplies: that two bowls with $2$ and $3$ beans take $8$ moves, that generate_beans(2) yields $289$ and $145$, and that those two heaps take $3419100$ moves. main runs them unless --skip-checkpoints is given; the Python and Java ports compute only the final value and carry no checkpoints.

All three programs assume the hypothesis of Section 7 instead of testing it, which is sound for this input but not in general: with an empty bowl between two occupied ones the difference of second moments can come out negative, as in Section 8, and the C++ conversion of a negative __int128 to unsigned __int128 then wraps to a huge value instead of reporting an error.

Complexity and Verification

Generating the heaps and accumulating their three moments are one pass each over the $n$ bowls, so $O(n)$ arithmetic operations, and what follows is a fixed number of them: two calls of sum_squares_arith and a few divisions. No value exceeds $2^{63}$ in magnitude, so every operation is on a number of bounded size, and memory is $O(n)$ for the stored heaps — $1500$ values here — plus a few wide integers. On the machine used here the whole process took $0.00$ s in C++, $0.01$ s in Python and $0.02$ s in Java, mostly start-up; in Python the generator and the moment pass together need about $0.2$ ms. The alternative is roughly $10^{17}$ single moves.

Beyond the three packaged checkpoints, the following was verified for this article.

The generator reproduces $b_1=289$ and $b_2=145$, continuing $1097,1573,1811,1930$.
Simulating the bowls with $2$ and $3$ beans takes $8$ moves, the second moment rising by $2$ each time, and ends at $\{-2,-1,1,2,3\}$; simulating the $434$ beans of the second example takes exactly $3419100$ moves and ends on bowls $-217$ to $217$ with bowl $-145$ empty, as Section 9 predicts.
All $3905$ unbroken blocks of one to five bowls holding one to five beans each, and $520$ random blocks of up to seven bowls with up to $60$ beans, were played out move by move: formula and predicted finishing position were right every time.
Section 5 was confirmed exhaustively for $1\le B\le6$ and $-12\le M\le12$: if $C$ is the sum of squares of the predicted set, a competing set with at most $C$ has every element within $\lfloor\sqrt C\rfloor$ of $0$, a window of at most $25$ integers here, and searching it the predicted set was always the unique minimiser.
The counts $u_i$ of Section 7 matched the simulated firing counts, and were never negative, on all $3905$ blocks above and in $300$ further random cases; for the $1500$-bowl input the nonzero $S_k$ change sign exactly once, so the counts are non-negative there too.
The single-bowl identity of Section 12 holds for all $n\le60$, against simulation up to $n=40$; and the C++, Python and Java programs print the same value, with the C++ checkpoints passing.

The simulations and brute-force searches are not part of the published solutions.

Footnotes and References

The references below supply the background facts used above. The moment identities, the cheapest finished position, the lemma on firing counts and the condition of Section 7 are derived explicitly in this article.

Project Euler 334 — Spilling the Beans. The official statement describes the row of bowls, the move that takes two beans from a bowl and gives one to each neighbour, and the end of the game when every bowl holds one bean or none. It defines t and b, states b₁ = 289 and b₂ = 145, illustrates the eight moves that finish two bowls holding 2 and 3 beans, gives 3419100 moves for b₁ and b₂ beans in adjacent bowls, and asks for the move count when 1500 adjacent bowls hold b₁ to b₁₅₀₀.
Wikipedia — Abelian sandpile model. The article describes toppling, in which an overloaded site gives one grain to each neighbour, states that the final stable configuration and each site's number of topplings do not depend on the order of toppling, and gives the least action principle: if u is the toppling vector of the actual stabilisation and n any integral vector that makes the configuration stable, then u(v) ≤ n(v) at every site.
Wikipedia — Chip-firing game. The article defines firing a vertex that holds at least as many chips as its degree, which on a line is exactly the move of this problem, and cites Björner, Lovász and Shor for the independence of the firing counts and the final stable state from the order of play.
Chip-Firing and Rotor-Routing on Directed Graphs. A. E. Holroyd, L. Levine, K. Mészáros, Y. Peres, J. Propp and D. B. Wilson, a self-contained survey of the abelian sandpile and rotor-router models on finite directed graphs. Its Lemma 2.2 shows that no vertex fires more often in any legal sequence than in one reaching a stable configuration, and that two legal stabilising sequences have the same length, final configuration and firing counts. Sections 6 and 7 add what the infinite line needs.
OEIS A000330 — square pyramidal numbers. The entry defines a(n) = 0² + 1² + ⋯ + n² = n(n+1)(2n+1)/6 and lists 0, 1, 5, 14, 30, 55, 91, 140. This closed form is the last term of the run identity of Section 10, and the single-bowl game of Section 12 takes a(⌊n/2⌋) moves.
Wikipedia — Bitwise operation. The article defines bitwise exclusive or as the operation whose result bit is 1 exactly where the two input bits differ, and notes that a right shift by one place is the floor of division by two — the two operations the generator uses.
cppreference — arithmetic operators states that integer division yields the quotient truncated towards zero and that (a / b) * b + a % b == a, so the remainder takes the sign of the dividend. The Python language reference states instead that floor division applies the floor function to the quotient. These conventions are why C++ and Java need a floor-division helper and Python does not.
GCC manual — 128-bit integers documents __int128 and unsigned __int128 as an extension on targets with a wide enough integer mode; the C++ accumulators use them. Java — BigInteger documents immutable arbitrary-precision integers and divideAndRemainder, and notes that dividing a negative by a positive gives a negative or zero remainder — the convention properFloorDiv and properFloorMod correct.

Problem 334 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i128 = __int128_t;
using u64 = std::uint64_t;
using u128 = unsigned __int128;

std::string to_string_u128(u128 value) {
    if (value == 0) {
        return "0";
    }
    std::string s;
    while (value > 0) {
        const int digit = static_cast<int>(value % 10);
        s.push_back(static_cast<char>('0' + digit));
        value /= 10;
    }
    std::reverse(s.begin(), s.end());
    return s;
}

std::vector<u64> generate_beans(const int count) {
    std::vector<u64> beans;
    beans.reserve(static_cast<std::size_t>(count));

    u64 t = 123456ULL;
    for (int i = 0; i < count; ++i) {
        if ((t & 1ULL) == 0ULL) {
            t /= 2ULL;
        } else {
            t = (t / 2ULL) ^ 926252ULL;
        }
        const u64 b = (t & ((1ULL << 11) - 1ULL)) + 1ULL;
        beans.push_back(b);
    }

    return beans;
}

i128 floor_div(const i128 a, const i128 b) {
    i128 q = a / b;
    i128 r = a % b;
    if (r < 0) {
        q -= 1;
    }
    return q;
}

i128 sum_squares_arith(const i128 first, const i128 n) {
    // Sum_{k=0}^{n-1} (first + k)^2
    if (n <= 0) {
        return 0;
    }
    const i128 sum_k = n * (n - 1) / 2;
    const i128 sum_k2 = n * (n - 1) * (2 * n - 1) / 6;
    return n * first * first + 2 * first * sum_k + sum_k2;
}

u128 moves_needed(const std::vector<u64>& beans) {
    i128 total = 0;
    i128 first_moment = 0;
    i128 second_moment = 0;

    for (i128 i = 0; i < static_cast<i128>(beans.size()); ++i) {
        const i128 b = static_cast<i128>(beans[static_cast<std::size_t>(i)]);
        total += b;
        first_moment += i * b;
        second_moment += i * i * b;
    }

    // In every move, second moment increases by exactly 2.
    // Stable final states are 0/1-occupancy sets with same total and first moment;
    // the attained stabilization is the minimum-second-moment such set.
    const i128 B = total;
    const i128 target_shift = first_moment - B * (B - 1) / 2;

    const i128 q = floor_div(target_shift, B);
    const i128 r = target_shift - q * B;  // 0 <= r < B

    const i128 n1 = B - r;
    const i128 n2 = r;

    // Final occupied positions:
    // q, q+1, ..., q+n1-1, q+n1+1, ..., q+B
    const i128 q_final = sum_squares_arith(q, n1) + sum_squares_arith(q + n1 + 1, n2);

    const i128 diff = q_final - second_moment;
    return static_cast<u128>(diff / 2);
}

bool run_checkpoints() {
    if (moves_needed(std::vector<u64>{2ULL, 3ULL}) != static_cast<u128>(8ULL)) {
        std::cerr << "Checkpoint failed: [2,3] should take 8 moves\n";
        return false;
    }

    const std::vector<u64> b2 = generate_beans(2);
    if (b2.size() != 2 || b2[0] != 289ULL || b2[1] != 145ULL) {
        std::cerr << "Checkpoint failed: b1/b2 generation\n";
        return false;
    }

    if (moves_needed(b2) != static_cast<u128>(3419100ULL)) {
        std::cerr << "Checkpoint failed: two-bowl sample moves\n";
        return false;
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    bool skip_checkpoints = false;
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            skip_checkpoints = true;
        } else {
            std::cerr << "Unknown argument: " << arg << '\n';
            return 1;
        }
    }

    if (!skip_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const std::vector<u64> beans = generate_beans(1500);
    const u128 answer = moves_needed(beans);
    std::cout << to_string_u128(answer) << '\n';
    return 0;
}

Python

def generate_beans(count):
    beans = []
    t = 123456
    for i in range(count):
        if (t & 1) == 0:
            t //= 2
        else:
            t = (t // 2) ^ 926252
        b = (t & ((1 << 11) - 1)) + 1
        beans.append(b)
    return beans

def sum_squares_arith(first, n):
    if n <= 0:
        return 0
    sum_k = n * (n - 1) // 2
    sum_k2 = n * (n - 1) * (2 * n - 1) // 6
    return n * first * first + 2 * first * sum_k + sum_k2

def moves_needed(beans):
    total = 0
    first_moment = 0
    second_moment = 0

    for i, b in enumerate(beans):
        total += b
        first_moment += i * b
        second_moment += i * i * b

    B = total
    target_shift = first_moment - B * (B - 1) // 2

    q = target_shift // B
    r = target_shift % B

    n1 = B - r
    n2 = r

    q_final = sum_squares_arith(q, n1) + sum_squares_arith(q + n1 + 1, n2)

    diff = q_final - second_moment
    return diff // 2

def solve():
    beans = generate_beans(1500)
    ans = moves_needed(beans)
    return str(ans)

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;
import java.math.BigInteger;

public class Euler334 {

    static List<Long> generateBeans(int count) {
        List<Long> beans = new ArrayList<>(count);
        long t = 123456;
        for (int i = 0; i < count; i++) {
            if ((t & 1) == 0) {
                t /= 2;
            } else {
                t = (t / 2) ^ 926252L;
            }
            long b = (t & ((1L << 11) - 1)) + 1;
            beans.add(b);
        }
        return beans;
    }

    static BigInteger sumSquaresArith(BigInteger first, BigInteger n) {
        if (n.compareTo(BigInteger.ZERO) <= 0)
            return BigInteger.ZERO;
        BigInteger two = BigInteger.valueOf(2);
        BigInteger six = BigInteger.valueOf(6);

        BigInteger nMinus1 = n.subtract(BigInteger.ONE);
        BigInteger sumK = n.multiply(nMinus1).divide(two);

        BigInteger twoNMinus1 = n.multiply(two).subtract(BigInteger.ONE);
        BigInteger sumK2 = n.multiply(nMinus1).multiply(twoNMinus1).divide(six);

        BigInteger term1 = n.multiply(first).multiply(first);
        BigInteger term2 = two.multiply(first).multiply(sumK);

        return term1.add(term2).add(sumK2);
    }

    static BigInteger floorDiv(BigInteger a, BigInteger b) {
        return a.divide(b); // In Java, BigInteger.divide truncates toward zero. But since both are positive
                            // here, it is actually floor division.
        // Wait, for negative 'a', it truncates toward zero instead of floor.
        // Let's implement proper floor div:
    }

    static BigInteger properFloorDiv(BigInteger a, BigInteger b) {
        BigInteger[] qr = a.divideAndRemainder(b);
        BigInteger q = qr[0];
        BigInteger r = qr[1];
        if (r.compareTo(BigInteger.ZERO) < 0) {
            if (b.compareTo(BigInteger.ZERO) > 0)
                q = q.subtract(BigInteger.ONE);
            else
                q = q.add(BigInteger.ONE);
        }
        return q;
    }

    static BigInteger properFloorMod(BigInteger a, BigInteger b) {
        BigInteger[] qr = a.divideAndRemainder(b);
        BigInteger r = qr[1];
        if (r.compareTo(BigInteger.ZERO) < 0) {
            if (b.compareTo(BigInteger.ZERO) > 0)
                r = r.add(b);
            else
                r = r.subtract(b);
        }
        return r;
    }

    public static String solve() {
        List<Long> beans = generateBeans(1500);

        BigInteger total = BigInteger.ZERO;
        BigInteger firstMoment = BigInteger.ZERO;
        BigInteger secondMoment = BigInteger.ZERO;

        for (int i = 0; i < beans.size(); i++) {
            BigInteger b = BigInteger.valueOf(beans.get(i));
            BigInteger ib = BigInteger.valueOf(i);

            total = total.add(b);
            firstMoment = firstMoment.add(ib.multiply(b));
            secondMoment = secondMoment.add(ib.multiply(ib).multiply(b));
        }

        BigInteger B = total;
        BigInteger bMinus1 = B.subtract(BigInteger.ONE);
        BigInteger bPair = B.multiply(bMinus1).divide(BigInteger.valueOf(2));

        BigInteger targetShift = firstMoment.subtract(bPair);

        BigInteger q = properFloorDiv(targetShift, B);
        BigInteger r = properFloorMod(targetShift, B);

        BigInteger n1 = B.subtract(r);
        BigInteger n2 = r;

        BigInteger qFinal = sumSquaresArith(q, n1).add(sumSquaresArith(q.add(n1).add(BigInteger.ONE), n2));

        BigInteger diff = qFinal.subtract(secondMoment);
        return diff.divide(BigInteger.valueOf(2)).toString();
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}