Problem 325: Stone Game II

Detailed mathematical approach

Problem Summary

Two players share two piles of stones. The player to move takes stones from the larger pile, and the number taken must be a positive multiple of the size of the smaller pile: from \((6,14)\), with \(6\) stones in the smaller pile and \(14\) in the larger, the legal removals are \(6\) and \(12\). Whoever takes all the stones of a pile wins. A configuration is winning if the player to move can force a win, and losing if the opponent can force a win whatever the player to move does. The statement gives \((1,5)\), \((2,6)\), \((3,12)\) as winning, since the larger pile can be emptied at once, and \((2,3)\), \((3,4)\) as losing. For a bound \(N\) we must add up \(x_i+y_i\) over all losing configurations \((x_i,y_i)\) with \(0\lt x_i\lt y_i\le N\),

$$S(N)=\sum_i\,(x_i+y_i),$$

and the task is \(S(10^{16})\bmod 7^{10}\), where \(7^{10}=282475249\). The statement supplies the checkpoints \(S(10)=211\) and \(S(10^4)=230312207313\). ^[1]

The whole solution in one sentence: a configuration is losing exactly when the ratio of the larger pile to the smaller is below the golden ratio \(\varphi\), so the losing partners of \(x\) are the \(\lfloor x/\varphi\rfloor\) integers just above \(x\), and the sum of those floors collapses into three self-similar sums that \(75\) recursive steps evaluate modulo \(7^{10}\).

Mathematical Approach

Every move lowers \(x+y\), so the game is finite and has no draws: each configuration is either winning or losing for the player to move. Sections 1 to 3 classify configurations by hand, Section 4 proves the pattern, and the rest turns it into a sum that about \(75\) recursive steps evaluate.

1. The moves available in a configuration

Write a configuration as \((x,y)\) with \(0\lt x\lt y\), so \(x\) is the smaller pile. A move replaces \(y\) by \(y-kx\) for some integer \(k\ge1\) with \(y-kx\ge0\), hence \(1\le k\le\lfloor y/x\rfloor\). Two remarks about these moves:

• If \(x\) divides \(y\), the choice \(k=y/x\) empties the larger pile and wins on the spot. This is why \((1,5)\), \((2,6)\) and \((3,12)\) are winning.
• If \(x\) does not divide \(y\), no single move can win, since \(y-kx=0\) is impossible. The move taking the most stones leaves \(r=y\bmod x\) with \(0\lt r\lt x\), so the piles become \(r\) and \(x\).

A move can leave two equal piles — from \((2,6)\), removing \(4\) stones gives \((2,2)\) — but only when \(y-kx=x\), which forces \(x\mid y\). Such configurations are settled as winning by the first bullet above, so the analysis that follows never has to leave the region \(x\lt y\).

2. A larger pile at least twice the smaller is always a win

Suppose \(y\ge 2x\), so \(\lfloor y/x\rfloor\ge2\). If \(x\mid y\) the player to move wins at once. Otherwise put \(r=y\bmod x\) with \(0\lt r\lt x\), and note that the player to move can reach both of the configurations \((r,x)\), by removing \(x\lfloor y/x\rfloor\) stones, and \((x,\,x+r)\), by removing \(x(\lfloor y/x\rfloor-1)\) stones; the second amount is a positive multiple of \(x\) exactly because \(\lfloor y/x\rfloor\ge2\). Now \((x,x+r)\) has only one legal move, since \(x+r\lt 2x\), and it lands on \((r,x)\). So one of the two configurations is winning and the other losing, whichever way round it falls, and the player to move can hand the opponent the losing one. Hence every configuration with \(y\ge2x\) is winning.

In the statement's example \((6,14)\) we have \(r=2\), and the reachable configurations are \((2,6)\), winning because \(2\mid6\), and \((6,8)\). So \((6,8)\) must be losing, and the right move is to take \(6\) stones, not \(12\).

3. Inside the narrow strip the game is forced

The remaining configurations satisfy \(x\lt y\lt 2x\). There \(k=2\) is already too big, so \(k=1\) is the only choice and the game is completely forced:

$$(x,y)\ \longmapsto\ (y-x,\;x).$$

This is one step of the subtractive Euclidean algorithm. The larger entry falls from \(y\) to \(x\), and since \(x\gt y/2\) two steps at least halve it, so a forced run ends after \(O(\log y)\) moves. For example \((5,8)\mapsto(3,5)\mapsto(2,3)\mapsto(1,2)\), and whoever moves from \((1,2)\) empties the larger pile; counting shows that the second player wins from \((5,8)\), so \((5,8)\) is losing. Among the configurations with \(y\le400\) the longest forced run is \(11\) moves, at the consecutive Fibonacci numbers \((233,377)\).

4. The golden-ratio criterion

Let \(\varphi=\tfrac{1+\sqrt5}{2}\) be the golden ratio, the positive root of \(\varphi^2=\varphi+1\); dividing that identity by \(\varphi\) gives the relation \(1/\varphi=\varphi-1\) used below. ^[3]

Claim. For \(0\lt x\lt y\), the configuration \((x,y)\) is losing for the player to move if and only if \(y\lt\varphi x\).

Proof by induction on \(x+y\). If \(y\ge 2x\), Section 2 makes \((x,y)\) winning, and indeed \(y/x\ge2\gt\varphi\). Otherwise \(x\lt y\lt 2x\); put \(d=y-x\), so \(0\lt d\lt x\). By Section 3 the only move leads to \((d,x)\), whose entries sum to less than \(x+y\), so the induction hypothesis applies to it. A configuration is losing exactly when every move leads to a winning one, and here there is one move, so \((x,y)\) is losing precisely when \((d,x)\) is winning — by the hypothesis, when \(x\gt\varphi d\), the equality \(x=\varphi d\) being impossible for irrational \(\varphi\). Finally \(x\gt\varphi d\) is the same as \(d\lt x/\varphi=(\varphi-1)x\), which rearranges to \(x+d\lt\varphi x\), that is \(y\lt\varphi x\) — the claim for \((x,y)\). \(\;\blacksquare\)

A check: \(\varphi\cdot5=8.0901\ldots\), so \((5,8)\) is losing, as the forced run above showed, while \((5,9)\) is winning — its single move leads to \((4,5)\), losing because \(5\lt\varphi\cdot4=6.47\ldots\). The game is the game of Euclid of Cole and Davie, 1969. ^[2]

5. The losing partners of a fixed smaller pile

Since \(y\) is an integer and \(\varphi x\) is irrational, \(y\lt\varphi x\) is the same as \(y\le\lfloor\varphi x\rfloor\). Writing \(y=x+d\) and using \(\varphi=1+1/\varphi\),

$$\begin{aligned}\lfloor\varphi x\rfloor&=x+\Bigl\lfloor\frac{x}{\varphi}\Bigr\rfloor=x+a_x,\\ a_x&=\Bigl\lfloor\frac{x}{\varphi}\Bigr\rfloor.\end{aligned}$$

So for each \(x\) the losing configurations are exactly \((x,x+d)\) with \(1\le d\le a_x\): a block of \(a_x\) consecutive values of \(y\) sitting directly above \(x\). The first values of \(a_x\), for \(x=1,2,\dots,10\), are

$$0,\,1,\,1,\,2,\,3,\,3,\,4,\,4,\,5,\,6 .$$

The entry \(a_1=0\) says that a pile of one stone has no losing partner, which agrees with Section 1. The companion sequence \(\lfloor\varphi x\rfloor\) is the lower Wythoff sequence, one half of the complementary Beatty pair generated by \(\varphi\) and \(\varphi^2\), ^[4] and \(a_x\) is the term of index \(x-1\) of Hofstadter's \(G\)-sequence, a sequence unrelated to the \(G(n)\) of Section 8. ^[5]

6. The requested sum as a double sum

A losing configuration contributes \(x+y=2x+d\). Only the bound \(y\le N\) can cut a block short, so with \(h_x=\min(a_x,\,N-x)\),

$$\begin{aligned}S(N)&=\sum_{x=1}^{N}\ \sum_{d=1}^{h_x}(2x+d)\\ &=\sum_{x=1}^{N}\Bigl(2x\,h_x+\frac{h_x(h_x+1)}{2}\Bigr).\end{aligned}$$

Evaluating this as written costs \(N\) steps, far too many, but it has already removed the game from the problem: only the floors \(a_x\) remain.

7. Where the bound bites: one cutoff

The block above \(x\) fits entirely below \(N\) when \(x+a_x=\lfloor\varphi x\rfloor\le N\), that is when \(\varphi x\lt N+1\), that is when

$$x\le c,\qquad c=\Bigl\lfloor\frac{N+1}{\varphi}\Bigr\rfloor,$$

both steps being equivalences because \(\varphi x\) and \((N+1)/\varphi\) are irrational. For \(x\le c\) we have \(h_x=a_x\); for \(x\gt c\) we have \(a_x\gt N-x\) and so \(h_x=N-x\). The sum splits into a prefix over \(x\le c\), which still carries the floors, and a tail over \(x\gt c\), which does not. For \(N=10\) the cutoff is \(c=6\); for the target it is \(c=6180339887498949\), whose digits are those of \(1/\varphi=0.6180339887498949\ldots\), as \(c\approx N/\varphi\) predicts.

8. The prefix: three weighted floor sums

For \(x\le c\) substitute \(h_x=a_x\) and introduce

$$\begin{aligned}G(n)&=\sum_{k=1}^{n}a_k,\\ P(n)&=\sum_{k=1}^{n}k\,a_k,\\ Q(n)&=\sum_{k=1}^{n}a_k^2 .\end{aligned}$$

Then the prefix is

$$\begin{aligned}&\sum_{x=1}^{c}\Bigl(2x\,a_x+\frac{a_x^2+a_x}{2}\Bigr)\\ &\qquad=\frac{4P(c)+Q(c)+G(c)}{2},\end{aligned}$$

and the division is exact because \(Q(c)+G(c)=\sum_{k\le c}a_k(a_k+1)\) is a sum of products of consecutive integers, hence even.

9. The tail in closed form

For \(x\gt c\) put \(t=N-x\). The inner sum is \(2xt+t(t+1)/2\), a polynomial in \(x\); expanding and multiplying by \(2\) gives

$$\begin{aligned}&2\Bigl(2xt+\frac{t(t+1)}{2}\Bigr)\\ &\qquad=N^2+N+(2N-1)x-3x^2 .\end{aligned}$$

Summing over \(c\lt x\le N\) therefore needs nothing but the counts and the two power sums

$$\Sigma_1=\sum_{x=c+1}^{N}x,\qquad \Sigma_2=\sum_{x=c+1}^{N}x^2,$$

each a difference of two closed forms, \(n(n+1)/2\) and \(n(n+1)(2n+1)/6\). The tail is half of

$$\begin{aligned}&(N-c)(N^2+N)\\ &\quad+(2N-1)\Sigma_1-3\Sigma_2,\end{aligned}$$

and it is an integer because each term \(2xt+t(t+1)/2\) is.

10. Three self-similar recurrences

Only \(G\), \(P\) and \(Q\) at \(n=c\) are still missing, and \(c\) is far too large for a loop. The key is to count by rows instead of columns. Picture the pairs \((k,j)\) with \(1\le j\le a_k\) as columns of heights \(a_k\): for \(n=6\) the heights are \(0,1,1,2,3,3\), so row \(j=1\) occupies \(k=2,\dots,6\), row \(j=2\) occupies \(k=4,5,6\) and row \(j=3\) occupies \(k=5,6\), and counting by rows gives \(G(6)=5+3+2=10\). Rows are easy to count because, for integers \(j\ge1\) and \(k\ge1\), the floor rule that \(j\le z\) is equivalent to \(j\le\lfloor z\rfloor\) ^[6] gives

$$\begin{aligned}j\le a_k&\iff j\le\frac{k}{\varphi}\iff k\ge\varphi j\\ &\iff k\ge\lfloor\varphi j\rfloor+1 .\end{aligned}$$

So the pairs \((k,j)\) with \(k\le n\) and \(1\le j\le a_k\) can be counted column by column in \(k\), which gives \(G(n)\), or row by row in \(j\), where row \(j\) contains \(n-\lfloor\varphi j\rfloor\) pairs and is non-empty exactly for \(j\le m\) with \(m=a_n\). Substituting \(\lfloor\varphi j\rfloor=j+a_j\) from Section 5 turns the row count into the same kind of sum one size smaller:

$$G(n)=nm-\frac{m(m+1)}{2}-G(m).$$

The same reflection with the weights \(a_k^2=\sum_{j\le a_k}(2j-1)\) and \(k\,a_k=\sum_{j\le a_k}k\) gives, with \(T(m)=\tfrac{m(m+1)}{2}\) and \(R(m)=\sum_{j\le m}j^2\),

$$\begin{aligned}Q(n)&=nm^2-2R(m)-2P(m)\\ &\quad+T(m)+G(m),\\ P(n)&=\frac{nm(n+1)}{2}-\frac{B(m)}{2},\end{aligned}$$

$$\begin{aligned}B(m)&=R(m)+2P(m)+Q(m)\\ &\quad+T(m)+G(m).\end{aligned}$$

Here \(B(m)=\sum_{j\le m}u_j(u_j+1)\) with \(u_j=j+a_j\), so \(B(m)\) is even and the halving exact; expanding \((2j-1)u_j\) and \(u_j(u_j+1)\) produces precisely the terms listed. The base case is \(G(0)=P(0)=Q(0)=0\). At \(n=6\), with \(m=3\) and \(G(3)=2\), \(P(3)=5\), \(Q(3)=2\), the recurrences return \(10\), \(46\) and \(24\), the values used in Section 11. Each recurrence reduces \(n\) to \(m=\lfloor n/\varphi\rfloor\), so the three sums at \(n\) cost constant work plus the three sums at roughly \(n/\varphi\), and the depth is about \(\log_\varphi n\). For the target the chain from \(c\) runs \(c,\,3819660112501051,\,\dots,\,1,\,0\): \(75\) steps, \(76\) calls in all.

11. A worked example: \(N=10\)

Here \(c=6\), and the blocks for \(x\le6\) are complete. Listing the surviving \(y\) and the inner sum \(2xh_x+h_x(h_x+1)/2\) for each \(x\):

• \(x=1\): \(a_1=0\), no losing partner, inner sum \(0\).
• \(x=2\): \(y=3\), inner sum \(5\).
• \(x=3\): \(y=4\), inner sum \(7\).
• \(x=4\): \(y=5,6\), inner sum \(19\).
• \(x=5\): \(y=6,7,8\), inner sum \(36\).
• \(x=6\): \(y=7,8,9\), inner sum \(42\).

The prefix is \(5+7+19+36+42=109\), and Section 8 agrees: \(G(6)=10\), \(P(6)=46\), \(Q(6)=24\), so \((4\cdot46+24+10)/2=109\). In the tail the blocks are cut — \(a_7=4\) but only \(y=8,9,10\) survive, \(a_8=4\) but only \(y=9,10\), \(a_9=5\) but only \(y=10\), and \(x=10\) contributes nothing — with inner sums \(48\), \(35\), \(19\) and a tail of \(102\). Section 9 reaches that without looking at individual \(x\): here \(N-c=4\), \(\Sigma_1=34\) and \(\Sigma_2=294\), so the tail is

$$\begin{aligned}&\frac{4\cdot110+19\cdot34-3\cdot294}{2}\\ &\qquad=\frac{204}{2}=102 .\end{aligned}$$

Altogether \(S(10)=109+102=211\), the checkpoint of the statement. The \(16\) losing configurations counted here are \((2,3)\), \((3,4)\), \((4,5)\), \((4,6)\), \((5,6)\), \((5,7)\), \((5,8)\), \((6,7)\), \((6,8)\), \((6,9)\), \((7,8)\), \((7,9)\), \((7,10)\), \((8,9)\), \((8,10)\) and \((9,10)\).

12. Exact floors, and working modulo \(7^{10}\)

Everything now rests on computing \(\lfloor n/\varphi\rfloor\) exactly, up to \(n=10^{16}+1\) for the cutoff. A plain double-precision division is not enough: at \(n=267914296\) it already returns \(165580141\) where the true floor is \(165580140\). Since \(1/\varphi=(\sqrt5-1)/2\),

$$\Bigl\lfloor\frac{n}{\varphi}\Bigr\rfloor=\Bigl\lfloor\frac{n\sqrt5-n}{2}\Bigr\rfloor=\Bigl\lfloor\frac{F-n}{2}\Bigr\rfloor,$$

where \(F=\lfloor n\sqrt5\rfloor=\lfloor\sqrt{5n^2}\rfloor\) is an integer square root. ^[8] The second equality deserves a line: write \(n\sqrt5=F+f\) with \(0\lt f\lt1\). If \(F-n\) is even, adding \(f/2\lt\tfrac12\) cannot reach the next integer; if it is odd, \((F-n)/2\) is a half-integer and adding \(f/2\) again stays below it. Either way the floor is the integer quotient of \(F-n\) by \(2\), as the code computes it.

Finally the answer is wanted modulo \(7^{10}\), which is not prime, so Fermat's little theorem does not apply — and is not needed. The formulas divide only by \(2\) and by \(6\), and \(\gcd(2,7)=\gcd(6,7)=1\), so both are invertible modulo \(7^{10}\) and the extended Euclidean algorithm produces the inverses. ^[7] Replacing every such division by a multiplication by the inverse carries the sums into the residues. Each reduced value then lies below \(7^{10}\), though the products formed before a reduction are larger, and the indices and the radicand \(5n^2\) stay outside this arithmetic.

How the Code Works

The C++ program fixes kTargetN\({}=10^{16}\) and kMod\({}=7^{10}\), and keeps the three floor sums in two small structures, BeattySumsExact for 128-bit integers and BeattySumsMod for residues, each with fields g, p and q.

isqrt_u128 implements the integer square root of Section 12: it seeds the result with a long double square root and then corrects it with two short loops, one raising the estimate while \((x+1)^2\le n\) and one lowering it while \(x^2\gt n\), so the returned value is exact whatever the seed was. floor_div_phi builds \(5n^2\) in 128 bits, applies that routine and returns \((F-n)/2\), while triangular_u128 and square_sum_u128 are the closed forms \(T(n)\) and \(R(n)\).

beatty_sums_exact is Section 10 transcribed: it computes \(m\), recurses on \(m\), and assembles \(G\), \(Q\) and \(P\) from the child values and from \(T(m)\), \(R(m)\). The order of the terms matters in unsigned arithmetic: in each expression the leading positive product dominates the subtractions that follow it, so no partial result underflows. Both halvings in this routine belong to the \(P\) recurrence and are exact, \(n(n+1)\) and \(B(m)\) being even; the halving of Section 8 happens later, in solve_exact.

The modular half mirrors this. mod_add, mod_sub and mod_mul keep every reduced value in \([0,\,7^{10})\), with mod_mul widening to 128 bits before reducing; mod_inverse is the extended Euclidean algorithm and supplies inv2 and inv6 once, which triangular_mod and square_sum_mod use instead of dividing. solve_exact and solve_mod are then Sections 7 to 9: cutoff \(c\) from floor_div_phi(n + 1), prefix \((4P+Q+G)/2\), an early return when \(c=n\) — which happens only for \(n=1\) — and otherwise the tail from \(N-c\), \(\Sigma_1\) and \(\Sigma_2\).

Two routines exist only for checking. is_winning_configuration plays the game of Sections 2 and 3: it returns as soon as \(y\bmod x=0\) or \(\lfloor y/x\rfloor\ge2\), and otherwise subtracts \(x\) once, reorders the piles and toggles a flip flag that records whose turn it is when the winning move appears. On the configurations it is passed, with \(0\lt x\lt y\), the test \(y\bmod x=0\) is redundant, since \(x\mid y\) already forces \(\lfloor y/x\rfloor\ge2\). brute_sum_by_game adds \(x+y\) over the losing configurations it finds, and run_validation_checkpoints compares that with solve_exact at \(N=220\), then checks \(S(10)\), \(S(10^4)\) and the agreement of the two paths at \(N=10^6\).

The Python and Java files carry the modular path alone, with no checkpoints. In Python, floor_div_phi uses math.isqrt and pow(2, -1, mod_val), pow(6, -1, mod_val) the inverses; integers are unbounded, and the recursion is \(76\) calls deep, far inside the default limit of \(1000\). In Java, floorDivPhi goes through BigInteger.sqrt, documented to return \(\lfloor\sqrt n\rfloor\) exactly, ^[9] and BigInteger.modInverse gives the inverses; the rest runs in long, safe because the modulus is below \(2^{29}\), so a product of two residues stays below \(2^{58}\).

Complexity and Verification

The target computation makes the \(76\) recursive calls of Section 10 — the \(75\) nonzero ones each a fixed number of multiplications, additions and one integer square root, the base call an immediate return — plus the cutoff and one evaluation of prefix and tail. Counting an operation on a whole number as one step, that is \(O(\log N)\) operations and \(O(\log N)\) words of stack; with unbounded integers the per-step cost also grows with the bit length. On the machine used here the Python version returns in about \(0.07\) milliseconds and the whole C++ program in about \(8\) milliseconds. Section 6 evaluated directly would need \(10^{16}\) steps, and brute_sum_by_game costs \(O(N^2\log N)\): \(N(N-1)/2\) configurations, each forced run at most \(O(\log N)\) moves. Hence the brute-force checkpoint stops at \(N=220\).

One limit of the exact path is worth naming, since the products are formed before the divisions: square_sum_u128(n) builds \(n(n+1)(2n+1)\) and only then divides by \(6\), and that product fits in unsigned 128-bit arithmetic ^[9] only for \(n\le5541191377756\). Simulating the wrap-around shows solve_exact already wrong at \(N=6\cdot10^{12}\) — far above the checkpoints it serves, far below the target — which is why the final run goes through solve_mod.

Beyond the checks the C++ file performs, the following was verified for this article.

• A direct search of the game tree reproduces the criterion of Section 4 for every configuration with \(0\lt x\lt y\le400\), and for all integers \(0\lt r\lt x\lt200\) exactly one of \((r,x)\) and \((x,x+r)\) is losing, as Section 2 needs.
• The identity \(x+a_x=\lfloor\varphi x\rfloor\) holds for all \(x\le2\cdot10^5\), the reflection identities of Section 10 for all \(n\lt1500\).
• The three recurrences agree with direct summation for \(n\le10^5\); the prefix-and-tail formula agrees with the \(O(N)\) sum of Section 6 for \(N\le10^6\) and with a game-by-game search for \(N\le1000\), giving \(S(100)=228757\), \(S(1000)=230172887\) and the two checkpoints.
• The modular path equals the exact path reduced modulo \(7^{10}\) at \(N=1\), \(10\), \(100\), \(10^4\), \(10^6\), \(10^7\), \(10^9\) and \(12345678901\). The published Python solver matches a game-by-game search for every \(N\le120\) and at \(N=220\), \(1000\), the Java solver for every \(N\le220\), and both reproduce \(S(10^4)\) modulo \(7^{10}\).

Footnotes and References

The references below supply the background facts; the golden-ratio criterion, the prefix–tail split and the three recurrences are derived in this article.

1. Project Euler 325 — Stone Game II. The official statement describes the two-pile game in which a player removes from the larger pile a positive multiple of the smaller pile and the player taking all the stones of a pile wins, gives (6, 14) with its legal removals 6 and 12, lists (1, 5), (2, 6), (3, 12) as winning and (2, 3), (3, 4) as losing, defines S(N) as the sum of x + y over the losing configurations with 0 < x < y ≤ N, states S(10) = 211 and S(10⁴) = 230312207313, and asks for S(10¹⁶) mod 7¹⁰.
2. Wikipedia — Euclidean algorithm. Its section on the game of Euclid records that Cole and Davie developed this two-player game in 1969, with the same rule — remove a multiple of the smaller pile from the larger — and the same winning condition, the first player to reduce a pile to zero stones. It states that the game has an optimal strategy without giving it, so Section 4 proves the criterion from scratch.
3. Wikipedia — Golden ratio. It gives φ = (1 + √5)/2 = 1.618033988749…, states that φ satisfies φ² = φ + 1, and singles out 1/φ = φ − 1 as a property unique to φ among the positive numbers. Both identities are used in Sections 4, 5 and 12, and the digits of 1/φ explain the cutoff of Section 7.
4. Wikipedia — Beatty sequence. It defines the Beatty sequence of an irrational r > 1 as the integers ⌊nr⌋, states Rayleigh's theorem that the sequences for r and s = r/(r − 1), which satisfy 1/r + 1/s = 1, place every positive integer in exactly one of them, and gives the golden-ratio case explicitly: the lower Wythoff sequence 1, 3, 4, 6, 8, 9, 11, 12, … for r = 1.618… against the upper one for s = 2.618…. The ⌊φx⌋ of Section 5 is that lower Wythoff sequence.
5. OEIS A005206 — Hofstadter G-sequence. The entry defines a(0) = 0, a(n) = n − a(a(n − 1)), lists 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, … and gives the closed form a(n) = ⌊σ(n + 1)⌋ with σ = (√5 − 1)/2 = 1/φ. Hence a(x − 1) = ⌊x/φ⌋, the block length of Section 5.
6. Wikipedia — Floor and ceiling functions. It defines ⌊x⌋ as the greatest integer not exceeding x and lists among its equivalences that, for an integer n, n ≤ x holds if and only if n ≤ ⌊x⌋ — the step that turns j ≤ a_k into k ≥ ⌊φj⌋ + 1 in Section 10.
7. Wikipedia — Modular multiplicative inverse. It states that an inverse of a modulo m exists if and only if gcd(a, m) = 1, that it is then unique modulo m, and that the extended Euclidean algorithm computes it in one pass from Bézout's identity — which is what Section 12 needs for 2 and 6 modulo 7¹⁰.
8. Wikipedia — Integer square root. It defines the integer square root of n as the greatest integer m with m ≤ √n, equivalently the x with x² ≤ n < (x + 1)², and describes the integer-only Newton iteration that needs no floating-point representation. Section 12 uses ⌊√(5n²)⌋ in that sense.
9. GCC manual — 128-bit integers. It documents unsigned __int128 on targets with an integer mode wide enough to hold 128 bits; the C++ file uses it for the exact sums and inside mod_mul. The Java port instead relies on BigInteger, whose sqrt returns the largest s with s² ≤ n.