Detailed mathematical approach

Problem Summary

A progressive number is a positive integer \(n\) for which there exists a divisor \(d\), a quotient \(q\), and a remainder \(r\) such that \(n=dq+r\), \(0<r<d\), and the three integers \(d\), \(q\), and \(r\) are consecutive terms of a geometric progression in some order. Problem 141 asks for the sum of all such \(n\le 10^{12}\) that are also perfect squares.

The difficulty is not checking one fixed \(n\); it is generating only the values that can possibly qualify. The implementations therefore avoid scanning all squares up to \(10^{12}\). Instead they parameterize every admissible geometric progression, turn the division identity into two explicit formulas for \(n\), and test only those candidates.

Mathematical Approach

The entire solution rests on a rigid description of three consecutive integer terms in a geometric progression. Once that description is written down, the condition \(n=dq+r\) produces only two algebraically distinct families.

Parameterizing the geometric progression

Let the common ratio be \(a/b>1\) in lowest terms, with \(\gcd(a,b)=1\) and \(a>b\). If the smallest term is \(x\), then the three consecutive terms are

$x,\quad x\frac{a}{b},\quad x\frac{a^2}{b^2}.$

For all three to be integers, \(x\) must be a multiple of \(b^2\), so we may write \(x=tb^2\) for some integer \(t\ge 1\). Therefore every admissible triple of positive integer GP terms has the form

$tb^2,\qquad tab,\qquad ta^2,$

with \(a>b\) and \(\gcd(a,b)=1\). This is exactly why the implementations iterate over coprime pairs \((a,b)\) with \(b<a\): they are enumerating reduced ratios, not guessing.

From the division data to two candidate families

Now place the divisor \(d\), quotient \(q\), and remainder \(r\) onto those three GP terms. Because \(0<r<d\), the remainder cannot be the largest term. That leaves two algebraically distinct possibilities.

If the remainder is the middle term, then the increasing order is

$q=tb^2,\qquad r=tab,\qquad d=ta^2.$

Substituting into \(n=dq+r\) gives

$n=t^2a^2b^2+tab=tab(tab+1).$

If the remainder is the smallest term, then \(r=tb^2\) and the other two GP terms are \(tab\) and \(ta^2\). Their product is the same no matter which one is \(d\) and which one is \(q\), so

$n=(tab)(ta^2)+tb^2=t^2a^3b+tb^2=tb(ta^3+b).$

So every progressive number must lie in one of the two families

$\boxed{n_1=tab(tab+1)},\qquad \boxed{n_2=tb(ta^3+b)},$

with \(a>b\), \(\gcd(a,b)=1\), and \(t\ge 1\). The implementations generate exactly these two formulas and then test whether the result is a square.

Worked Example

Take \(a=2\), \(b=1\), \(t=1\). The GP terms are \(1,2,4\).

If the remainder is the smallest term, choose \(r=1\), \(d=2\), \(q=4\). Then

$n=dq+r=2\cdot 4+1=9,$

and \(9\) is a perfect square. This is the smallest progressive square.

If instead the remainder is the middle term, choose \(q=1\), \(r=2\), \(d=4\). Then

$n=dq+r=4\cdot 1+2=6,$

which is progressive but not a square. This shows why the square condition is handled as a separate test after generating the progressive candidates.

Why the search space is finite

For both families the dominant term is at least \(t^2a^2b^2\). In the second family we even have \(t^2a^3b>t^2a^2b^2\) because \(a>b\). Therefore any admissible triple must satisfy

$t^2a^2b^2\le N,$

where \(N=10^{12}\).

That yields the exact loop bounds used by the implementations:

$1\le a,\qquad 1\le b<a,\qquad a^2b^2\le N,\qquad 1\le t\le \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor.$

Within those bounds, each triple produces at most two candidate values, one from each family. Any candidate above \(N\) is discarded immediately. The conditions \(a>b\) and \(\gcd(a,b)=1\) remove redundant descriptions of the same ratio, so the enumeration is mathematically complete without being bloated by obvious duplicates.

How the Code Works

Generate admissible progressive candidates

The C++, Python, and Java implementations loop over all coprime pairs \((a,b)\) with \(b<a\), then over all scale factors \(t\) compatible with the bound \(t^2a^2b^2\le 10^{12}\). For each triple they evaluate the two formulas \(n_1\) and \(n_2\). This step is a direct translation of the derivation above; there is no trial division over arbitrary \(n\).

Test squares and accumulate unique values

Every candidate is checked with an integer square-root test. If the square of the integer root equals the candidate, the value is kept. Because the same square can arise from more than one progressive decomposition, the valid values are stored in a set before summation. After the enumeration ends, the implementations sum the distinct progressive squares and return that total.

Complexity Analysis

Let \(N\) be the upper bound. The number of generated parameter triples is

$\sum_{\substack{a\ge 1\\ b<a\\ ab\le \sqrt{N}\\ \gcd(a,b)=1}} \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor,$

and each triple causes only constant-time arithmetic, up to two square tests, and set insertions. This is far smaller than scanning all integers or all squares up to \(N\), and it is well within range for \(N=10^{12}\).

A convenient asymptotic summary is that the enumeration is roughly \(O(\sqrt{N}\log^2 N)\), while memory usage is \(O(S)\), where \(S\) is the number of distinct progressive squares found. In practice \(S\) is tiny, so memory consumption stays negligible.

Footnotes and References

1. Problem page: Project Euler 141
2. Division algorithm: Wikipedia - Division algorithm
3. Geometric progression: Wikipedia - Geometric progression
4. Greatest common divisor: Wikipedia - Greatest common divisor
5. Square number: Wikipedia - Square number
6. Integer square root: Wikipedia - Integer square root