Detailed mathematical approach

Problem Summary

A positive integer \(k\) is called a square-pivot if there exist integers \(m>0\) and \(n\ge k\) such that

$ (k-m)^2+(k-m+1)^2+\cdots+k^2=(n+1)^2+(n+2)^2+\cdots+(n+m)^2. $

So the \((m+1)\) consecutive squares ending at \(k\) must equal the \(m\) consecutive squares starting just after \(n\).

The task is to sum all distinct square-pivots

$ k\le L, $

with \(L=10^{10}\) in the full problem. The code does not brute-force all triples \((k,m,n)\); it converts the condition into a Pell-equation pipeline.

Mathematical Approach

1. Expanding the Square-Sum Identity

Start from

$ \sum_{i=0}^{m}(k-i)^2=\sum_{j=1}^{m}(n+j)^2. $

Using the standard sum-of-squares formula, the left side becomes

$ (m+1)k^2-km(m+1)+\frac{m(m+1)(2m+1)}{6}, $

while the right side becomes

$ mn^2+m(m+1)n+\frac{m(m+1)(2m+1)}{6}. $

The cubic tail cancels immediately, leaving the key Diophantine relation

$ (m+1)k(k-m)=m\,n(n+m+1). $

This is the real starting point of the implementation.

2. Quadratic Viewpoint and the Brute-Force Check

For fixed \(k\) and \(m\), we can treat the previous identity as a quadratic equation in \(n\):

$ n^2+(m+1)n-\frac{(m+1)k(k-m)}{m}=0. $

Therefore \(n\) is integral if and only if the discriminant

$ \Delta=(m+1)^2+4\frac{(m+1)k(k-m)}{m} $

is a perfect square and the parity matches.

This is exactly what the checkpoint function brute_pivots tests: it loops over \(k\) and \(m\), computes \(\Delta\), checks whether \(\sqrt{\Delta}\) is integral, and then reconstructs \(n\).

3. A Symmetric Quadratic Form

Introduce the shifted variables

$ A=2n+m+1,\qquad B=2k-m. $

Then

$ n(n+m+1)=\frac{A^2-(m+1)^2}{4}, $

and

$ k(k-m)=\frac{B^2-m^2}{4}. $

Substituting these into the previous identity gives

$ mA^2-(m+1)B^2=m(m+1). $

This is much closer to Pell form, because the inhomogeneous right-hand side is exactly the product \(m(m+1)\).

4. Squarefree Decomposition and Pell Reduction

Write

$ m(m+1)=s q^2, $

where \(s\) is squarefree and \(q\) is the square part.

Now make the linear substitution

$ A=(m+1)x+qsy,\qquad B=mx+qsy. $

A direct expansion shows that

$ mA^2-(m+1)B^2=s q^2(x^2-sy^2). $

But the left side must equal \(m(m+1)=s q^2\). After cancelling \(s q^2\), we obtain the Pell equation

$ x^2-sy^2=1. $

So for a fixed \(m\), admissible pivots come from solutions of the Pell equation attached to the squarefree part of \(m(m+1)\).

5. Recovering \(k\) and \(n\) from Pell Solutions

Since \(B=2k-m\) and \(A=2n+m+1\), the inverse formulas are

$ k=\frac{mx+qsy+m}{2}, $

$ n=\frac{(m+1)x+qsy-(m+1)}{2}. $

Also

$ x=A-B=2(n-k+m)+1. $

This immediately explains three filters in the code:

1. \(x\) must be odd, because \(2(n-k+m)+1\) is odd,

2. \(n\ge k\) is equivalent to \(x\ge 2m+1\),

3. the numerator of the formula for \(k\) must be even so that \(k\) is integral.

The C++ code implements these as sol.x >= 2m+1, oddness of sol.x, and a final parity check on the numerator.

6. Worked Examples

The official examples fall out naturally from the Pell parametrization.

For \(m=1\), we have

$ m(m+1)=2=2\cdot 1^2, $

so \(s=2\) and \(q=1\). The Pell equation is

$ x^2-2y^2=1. $

The solution \((x,y)=(3,2)\) gives

$ k=\frac{1\cdot 3+1\cdot 2\cdot 2+1}{2}=4,\qquad n=\frac{2\cdot 3+1\cdot 2\cdot 2-2}{2}=4. $

The next Pell solution \((17,12)\) gives

$ k=\frac{17+24+1}{2}=21,\qquad n=\frac{34+24-2}{2}=28. $

For \(m=3\),

$ m(m+1)=12=3\cdot 2^2, $

so \(s=3\), \(q=2\), and the Pell solution \((x,y)=(7,4)\) gives

$ k=\frac{3\cdot 7+2\cdot 3\cdot 4+3}{2}=24. $

For \(m=2\), we get \(s=6\), \(q=1\), and \((x,y)=(49,20)\) gives

$ k=\frac{2\cdot 49+6\cdot 20+2}{2}=110. $

These recover the sample pivots \(4\), \(21\), \(24\), and \(110\).

7. Why the Code's Bounds Are Correct

The implementation does not let \(m\) run arbitrarily.

Because \(n\ge k\), we have

$ n(n+m+1)\ge k(k+m+1). $

Combining this with

$ (m+1)k(k-m)=m\,n(n+m+1) $

gives

$ (m+1)k(k-m)\ge m k(k+m+1). $

After dividing by \(k>0\), this simplifies to

$ k\ge 2m(m+1). $

Therefore, if \(k\le L\), then necessarily

$ 2m(m+1)\le L. $

This yields the code's bound

$ m\le \left\lfloor\frac{\sqrt{2L+1}-1}{2}\right\rfloor. $

There is also an \(x\)-bound. Since

$ k=\frac{mx+qsy+m}{2}\ge \frac{mx+m}{2}, $

the condition \(k\le L\) implies

$ x\le \frac{2L-m}{m}. $

This is exactly the per-entry bound stored as x_max.

8. Why Grouping by Squarefree Part Matters

Different values of \(m\) can have the same squarefree part \(s\) in the factorization of \(m(m+1)\).

Since the Pell equation depends only on \(s\), the code groups all such \(m\) together, solves the Pell equation once for that \(s\), and reuses the entire Pell solution stream for every entry in the group.

This is the main asymptotic improvement over solving a fresh Pell problem for every \(m\).

Different \((m,n)\) pairs can even produce the same pivot \(k\). For example, the pivot

$ 684 $

occurs both with \((m,n)=(4,760)\) and with \((m,n)=(18,684)\). That is why the final pivot list must be globally sorted and deduplicated.

How the Code Works

The function build_primes constructs a prime list for factor support. The helper squarefree_and_square_part writes each number as \(s q^2\) with squarefree \(s\).

For each admissible \(m\), the code computes \(n=m(m+1)\), extracts its squarefree part \(s\) and square part \(q\), computes the safe bound x_max, and stores the triple \((m,q,x_{\max})\) in a hash map keyed by \(s\).

The function find_fundamental_pell_limited uses continued fractions to find the fundamental Pell solution, and pell_solutions_up_to generates all further solutions by the standard Pell recurrence

$ x_{t+1}=x_1x_t+s y_1y_t,\qquad y_{t+1}=x_1y_t+y_1x_t. $

For each group with the same \(s\), the solver generates Pell solutions once up to the largest needed \(x\), then maps them back to candidate pivots with

$ k=\frac{mx+qsy+m}{2}. $

Finally it filters by oddness, lower bound, parity, and \(k\le L\), stores all hits in one vector, sorts them, removes duplicates, and sums them.

The checkpoint routine compares the fast method with brute force up to \(5000\) and also verifies that the sample pivots \(4,21,24,110\) appear below \(120\).

Complexity Analysis

The preprocessing range for \(m\) is only

$ m\le O(\sqrt{L}), $

and each such \(m\) is factorized once. The dominant work is then the Pell generation for each distinct squarefree class \(s\), together with the mapping and filtering of those solutions for every member of the group.

Memory usage is dominated by:

1. the grouping table keyed by squarefree part,

2. the temporary Pell solution list for one group,

3. the final vector of distinct pivots.

The critical practical idea is not a closed form for the entire problem, but the reduction from a three-parameter search \((k,m,n)\) to reusable Pell streams indexed by squarefree classes.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=261
2. Sum of squares formula: Wikipedia - square pyramidal number
3. Pell equations: Wikipedia - Pell's equation
4. Continued fractions and Pell solvers: Wikipedia - continued fraction
5. Squarefree integers: Wikipedia - square-free integer