Detailed mathematical approach

Problem Summary

For each \(n\), the repository code computes a value \(m(n)\) and then adds \(m(n)^3\) to the global sum $\sum_{n=1}^{1000} m(n)^3.$ The important point is that the local solutions do not use a short closed form. Instead they model the game by repeatedly composing residue maps on \(R_n=\{0,1,\dots,n\}\) and stop as soon as the diagonal row becomes constant. The checkpoints hard-coded in all three implementations are \(m(2)=2\), \(m(7)=1\), \(m(20)=4\), and \(\sum_{n=1}^{20} m(n)^3=8150\).

Mathematical Approach

Step 1: Residues and the Overflow-to-Zero Shift

Fix \(n\) and set \(M=n+1\). Every table entry is a function value on the residue set \(R_n=\{0,1,\dots,n\}\). The code does not use ordinary addition modulo \(M\). Instead it uses the truncated shift

$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$

That distinction matters: ordinary modular addition would send \(M-1+k\) to \(k-1\), but the program sends every overflow directly to \(0\). This is exactly what the line if (value >= step) value = 0; implements in C++, Python, and Java.

Step 2: The Clean Recurrence Behind the Two Tables

Let \(F_s^{(m)}:R_n \to R_n\) denote the map stored in row \(m\) after stage \(s\) has finished. Row \(0\) is always the identity map:

$F_s^{(0)}(v)=v.$

The code initializes stage \(0\) with \(F_0^{(0)}=\mathrm{id}\), and for every later stage it builds row \(m\) from the previous row of the current stage and the previous row of the previous stage. Written mathematically, the update is

$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$

Evaluated at a residue \(v\), this becomes

$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right).$

In particular, \(F_s^{(1)}=\sigma_s\), so the first row of every stage is just the raw truncated shift. This recurrence is the mathematical core of the implementation; there is no hidden algebraic shortcut in the source files.

Step 3: Diagonal Rows and the Definition of \(m(n)\)

After stage \(s\), the program inspects the diagonal row \(F_s^{(s)}\). If every residue gives the same output, then the row has collapsed to a constant map:

$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$

The solver then returns that constant \(c\), which is exactly the value denoted by \(m(n)\) in the code path. So the algorithm searches for the first stage at which repeated composition of these truncated shifts destroys all dependence on the starting residue.

The search is guaranteed to succeed by stage \(M=n+1\). Indeed, \(\sigma_M\) is already the constant-zero map, hence \(F_M^{(1)}\) is constant. If \(F_M^{(m-1)}\) is constant, then \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) is also constant, so applying \(F_{M-1}^{(m-1)}\) still gives a constant. By induction, every row of stage \(M\) is constant, especially the diagonal row \(F_M^{(M)}\).

Step 4: Worked Example \(n=2\)

For \(n=2\), we work on \(R_2=\{0,1,2\}\) with \(M=3\). The first-stage row is simply \(F_1^{(1)}=\sigma_1\), so

$F_1^{(1)}=[1,2,0].$

At stage \(2\), the first row is \(F_2^{(1)}=\sigma_2=[2,0,0]\). The second row becomes

$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right),$

which yields

$F_2^{(2)}=[1,2,2].$

This row is not constant, so the algorithm continues. At stage \(3\), \(\sigma_3\) is the constant-zero map, hence

$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$

The diagonal row is now constant, so \(m(2)=2\), exactly matching the validation embedded in every solution file.

Step 5: What the Program Sums

The outer driver runs this procedure for every \(1 \le n \le 1000\) and accumulates

$\sum_{n=1}^{1000} m(n)^3.$

Before trusting the long run, the implementations verify the small checkpoints \(m(2)=2\), \(m(7)=1\), \(m(20)=4\), and the partial cube-sum \(8150\) through \(n=20\). Those checks are important because the recurrence is subtle and because the allocated table buffers are reused across successive \(n\)-values for efficiency.

How the Code Works

The C++ version stores the two tables in flat arrays and addresses row \(m\), column \(v\) by index(m, v) = (m << SHIFT) + v with SHIFT = 10. Since \(2^{10}=1024 > 1000\), each logical row fits in a fixed stride of 1024 entries. Python uses the same flattened indexing, and Java mirrors the same memory layout with two int[] buffers.

Inside compute_m or computeM, row 0 is the identity map. For each stage s, the code fills rows 1 through s using the recurrence above, tests whether row s is constant, and swaps the two work buffers if another stage is needed. The three languages therefore implement the same mathematics with only syntactic differences: pointer swapping in C++, tuple reassignment in Python, and reference swapping in Java.

Complexity Analysis

For a fixed \(n\), the inner update performs one constant-time transition for every triple \((s,m,v)\) with \(1 \le s \le n+1\), \(1 \le m \le s\), and \(0 \le v \le n\). Therefore

$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$

The constant-row check adds only \(O(n)\) per stage and does not change the order. The logical table size is two arrays of roughly \((n+1)^2\) entries, so the working memory is \(O(n^2)\). In the repository implementation, this is realized with two fixed \(1024 \times 1024\) buffers because the maximum requested \(n\) is \(1000\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=391
2. Modular arithmetic background: Wikipedia — Modular arithmetic
3. Function composition: Wikipedia — Function composition
4. Dynamic programming background: Wikipedia — Dynamic programming