Detailed mathematical approach

Problem Summary

This problem comes from a lattice-point configuration involving a parabola and a line. After the geometric reduction used by the implementation, the remaining task is to evaluate an exact arithmetic counting function \(S(N)\). The Project Euler target is the residue of \(S(10^{12})\) modulo \(10^8\).

The important point is that the implementation never enumerates lattice points one by one. Instead, it uses a closed formula made of a fixed polynomial part and a quotient-dependent summation whose values are grouped into floor-division blocks.

Mathematical Approach

Step 1: Polynomial Prefix Functions

The reduced counting formula is built from three polynomial prefix functions:

$P_1(t)=\frac{(t^2-t+6)(t+1)}{6},$

$P_2(t)=\frac{(t^2-t+12)(t+1)(t+2)}{24},$

$P_3(t)=\frac{(t^2-t+20)(t+1)(t+2)(t+3)}{120}.$

Expanding them shows that they are cubic, quartic, and quintic polynomials:

$P_1(t)=\frac{t^3+5t+6}{6},\qquad P_2(t)=\frac{t^4+2t^3+11t^2+34t+24}{24},$

$P_3(t)=\frac{t^5+5t^4+25t^3+115t^2+214t+120}{120}.$

What matters computationally is their telescoping behavior:

$P_1(t)-P_1(t-1)=\frac{t(t-1)}{2}+1,$

$P_2(t)-P_2(t-1)=P_1(t),\qquad P_3(t)-P_3(t-1)=P_2(t).$

So \(P_2\) is a prefix sum of \(P_1\), and \(P_3\) is a prefix sum of \(P_2\). This is exactly why long ranges can later be collapsed to differences of polynomial values.

Step 2: Boundary Values and Why Negative Arguments Are Safe

The formulas also satisfy convenient zero values:

$P_2(-1)=P_2(-2)=0,\qquad P_3(-1)=P_3(-2)=P_3(-3)=0.$

These vanishings are not accidental: they come from the explicit factors \((t+1)(t+2)\) in \(P_2\) and \((t+1)(t+2)(t+3)\) in \(P_3\). As a result, the same telescoping identities remain valid even when a boundary term lands just below zero. That allows the implementation to use one uniform arithmetic formula at block boundaries without adding special cases.

Step 3: The Exact Reduced Formula

After the geometric part has been reduced away, the exact count has the form

$S(N)=B(N)+\sum_{m=2}^{N-1} H_N(m),$

where the fixed base contribution is

$B(N)=P_2(N)+P_2(N+1)+P_2(N-2)+P_1(N)+P_1(N+1).$

For each integer \(m\) in the remaining sum, define the quotient

$q=\left\lfloor\frac{N}{m}\right\rfloor.$

The summand is then piecewise:

$H_N(m)= \begin{cases} P_2(m+q)+P_2(q-m), & m\le q,\\ P_2(m+q)-P_2(m-q-1), & m\gt q. \end{cases}$

This is the exact arithmetic content used by the C++, Python, and Java implementations. The two branches correspond to the two regimes on opposite sides of the diagonal \(m=q\), equivalently on opposite sides of \(\sqrt N\).

Step 4: Why Floor-Division Blocks Appear

The expensive-looking term is the quotient \(q=\lfloor N/m\rfloor\). But \(q\) is constant on intervals of consecutive \(m\)-values. If a block begins at \(L\), then the common quotient is

$q=\left\lfloor\frac{N}{L}\right\rfloor,$

and the block ends at

$R=\left\lfloor\frac{N}{q}\right\rfloor.$

Therefore every \(m\in[L,R]\) shares the same quotient \(q\). The classic fact behind this technique is that \(\lfloor N/m\rfloor\) takes only \(O(\sqrt N)\) distinct values, which turns the summation into a block computation rather than a linear scan.

Step 5: Telescoping One Whole Block at Once

Because \(P_3\) is a prefix sum of \(P_2\), each block can be collapsed in constant time.

If the block lies entirely in the region \(m\le q\), then

$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)+P_2(q-m)\bigr).$

Applying the prefix identity twice gives

$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)+P_3(q-L)-P_3(q-R-1).$

If the block lies entirely in the region \(m\gt q\), then

$\sum_{m=L}^{R} H_N(m)=\sum_{m=L}^{R}\bigl(P_2(m+q)-P_2(m-q-1)\bigr),$

so

$\sum_{m=L}^{R} H_N(m)=P_3(R+q)-P_3(L+q-1)-P_3(R-q-1)+P_3(L-q-2).$

Each quotient block lies wholly on one side of the diagonal. Indeed, blocks with \(m\le q\) are exactly the ones in the small-\(m\) region \(m\le \sqrt N\), while blocks with \(m\gt q\) lie in the large-\(m\) region \(m\gt \sqrt N\). That is why one branch choice per block is enough.

Step 6: Worked Example \(S(5)\)

First evaluate the base term:

$P_2(5)=56,\qquad P_2(6)=98,\qquad P_2(3)=15,\qquad P_1(5)=26,\qquad P_1(6)=42,$

hence

$B(5)=56+98+15+26+42=237.$

Now process the quotient blocks.

For \(m=2\), we have \(q=\lfloor 5/2\rfloor=2\), so this is the \(m\le q\) case:

$H_5(2)=P_2(4)+P_2(0)=30+1=31.$

For \(m=3,4\), the quotient is \(q=1\). This is a single \(m\gt q\) block with \(L=3\) and \(R=4\):

$\sum_{m=3}^{4} H_5(m)=P_3(5)-P_3(3)-P_3(2)+P_3(0).$

Using \(P_3(5)=112\), \(P_3(3)=26\), \(P_3(2)=11\), and \(P_3(0)=1\), we get

$\sum_{m=3}^{4} H_5(m)=112-26-11+1=76.$

Therefore

$S(5)=237+31+76=344,$

which matches the checkpoint used by the implementation. A second checkpoint is

$S(100)=26709528.$

How the Code Works

The C++, Python, and Java implementations all follow the same strategy. They evaluate the fixed base term once, then sweep the remaining range by quotient blocks rather than by individual indices. For each block, they compute one shared floor quotient, determine the block endpoint from that quotient, and add the corresponding telescoped \(P_3\)-difference formula.

The sum is kept exact throughout. Only after the full integer value of \(S(N)\) has been assembled do the implementations reduce it modulo \(10^8\). That is essential because the exact count for \(N=10^{12}\) is far larger than ordinary machine integers can hold safely.

Complexity Analysis

The number of distinct values of \(\lfloor N/m\rfloor\) is \(O(\sqrt N)\). Each block requires only a constant number of polynomial evaluations and integer additions/subtractions, so the total running time is

$O(\sqrt N).$

The algorithm stores only a fixed amount of state apart from arbitrary-precision integer temporaries, so the memory usage is \(O(1)\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=403
2. Finite differences and discrete summation: Wikipedia — Finite difference
3. Floor-division block splitting: Wikipedia — Dirichlet hyperbola method
4. Lattice-point background: Wikipedia — Lattice point
5. Parabola-line geometry: Wikipedia — Parabola