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.
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.
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.
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.
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.
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.
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\).
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.
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.
Eine progressive Zahl ist eine positive ganze Zahl \(n\), für die es einen Divisor \(d\), einen Quotienten \(q\) und einen Rest \(r\) mit \(n=dq+r\) und \(0<r<d\) gibt, so dass \(d\), \(q\) und \(r\) in irgendeiner Reihenfolge drei aufeinanderfolgende Glieder einer geometrischen Folge sind. In Problem 141 soll die Summe aller solchen \(n\le 10^{12}\) bestimmt werden, die zusätzlich perfekte Quadrate sind.
Die eigentliche Schwierigkeit besteht nicht darin, eine einzelne Zahl zu testen, sondern nur die Werte zu erzeugen, die überhaupt in Frage kommen. Deshalb durchsuchen die Implementierungen nicht alle Quadratzahlen bis \(10^{12}\), sondern parametrisieren jede zulässige geometrische Folge, leiten daraus zwei explizite Formeln für \(n\) ab und prüfen nur diese Kandidaten.
Der gesamte Lösungsweg beruht auf einer starren Beschreibung von drei aufeinanderfolgenden ganzzahligen Gliedern einer geometrischen Folge. Sobald diese Form feststeht, reduziert sich die Bedingung \(n=dq+r\) auf nur zwei algebraisch verschiedene Familien.
Schreibe das gemeinsame Verhältnis in vollständig gekürzter Form als \(a/b>1\), mit \(\gcd(a,b)=1\) und \(a>b\). Ist das kleinste Glied gleich \(x\), dann lauten die drei aufeinanderfolgenden Glieder
$$x,\quad x\frac{a}{b},\quad x\frac{a^2}{b^2}.$$
Damit alle drei Werte ganzzahlig sind, muss \(x\) ein Vielfaches von \(b^2\) sein. Also kann man \(x=tb^2\) mit \(t\ge 1\) schreiben. Jede zulässige ganzzahlige GP hat daher die Form
$$tb^2,\qquad tab,\qquad ta^2,$$
wobei \(a>b\) und \(\gcd(a,b)=1\) gilt. Genau deshalb durchlaufen die Implementierungen teilerfremde Paare \((a,b)\) mit \(b<a\): Das sind die gekürzten Verhältnisse der geometrischen Folge.
Nun werden Divisor \(d\), Quotient \(q\) und Rest \(r\) auf diese drei GP-Glieder verteilt. Wegen \(0<r<d\) kann der Rest nicht das größte Glied sein. Übrig bleiben also genau zwei algebraisch verschiedene Fälle.
Ist der Rest das mittlere Glied, dann gilt in aufsteigender Reihenfolge
$$q=tb^2,\qquad r=tab,\qquad d=ta^2.$$
In \(n=dq+r\) eingesetzt ergibt das
$$n=t^2a^2b^2+tab=tab(tab+1).$$
Ist der Rest das kleinste Glied, dann ist \(r=tb^2\) und die beiden anderen GP-Glieder sind \(tab\) und \(ta^2\). Ihr Produkt ist unabhängig davon, welches davon der Divisor und welches der Quotient ist. Also erhält man
$$n=(tab)(ta^2)+tb^2=t^2a^3b+tb^2=tb(ta^3+b).$$
Damit liegt jede progressive Zahl in einer der beiden Familien
$$\boxed{n_1=tab(tab+1)},\qquad \boxed{n_2=tb(ta^3+b)},$$
mit \(a>b\), \(\gcd(a,b)=1\) und \(t\ge 1\). Genau diese beiden Formeln erzeugen die Implementierungen, bevor anschließend auf Quadratzahl getestet wird.
Nimm \(a=2\), \(b=1\), \(t=1\). Die drei GP-Glieder sind dann \(1,2,4\).
Wenn der Rest das kleinste Glied ist, wähle \(r=1\), \(d=2\), \(q=4\). Dann ist
$$n=dq+r=2\cdot 4+1=9,$$
und \(9\) ist ein perfektes Quadrat. Das ist die kleinste progressive Quadratzahl.
Wenn stattdessen der Rest das mittlere Glied ist, erhält man \(q=1\), \(r=2\), \(d=4\). Dann folgt
$$n=dq+r=4\cdot 1+2=6,$$
also eine progressive Zahl, aber kein Quadrat. Das zeigt, warum die Quadrateigenschaft separat geprüft werden muss.
In beiden Familien ist der führende Term mindestens \(t^2a^2b^2\). In der zweiten Familie gilt sogar \(t^2a^3b>t^2a^2b^2\), weil \(a>b\). Also muss jedes zulässige Tripel die Ungleichung
$$t^2a^2b^2\le N$$
erfüllen, wobei \(N=10^{12}\) ist.
Daraus ergeben sich genau die Schleifengrenzen der Implementierungen:
$$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.$$
Innerhalb dieser Grenzen liefert jedes Tripel höchstens zwei Kandidaten, je einen aus jeder Familie. Werte oberhalb von \(N\) werden sofort verworfen. Die Bedingungen \(a>b\) und \(\gcd(a,b)=1\) entfernen redundante Beschreibungen desselben Quotienten und machen die Enumeration vollständig, aber nicht unnötig aufgebläht.
Die C++-, Python- und Java-Implementierungen iterieren über alle teilerfremden Paare \((a,b)\) mit \(b<a\) und anschließend über alle Skalierungsfaktoren \(t\), die die Schranke \(t^2a^2b^2\le 10^{12}\) erfüllen. Für jedes Tripel werden die beiden Formeln \(n_1\) und \(n_2\) ausgewertet. Das ist eine direkte Umsetzung der Herleitung; ein blinder Test beliebiger \(n\) findet nicht statt.
Jeder Kandidat wird mit einem ganzzahligen Quadratwurzeltest überprüft. Nur wenn das Quadrat der ganzzahligen Wurzel wieder genau den Kandidaten ergibt, wird der Wert übernommen. Weil dieselbe Quadratzahl aus mehr als einer progressiven Darstellung entstehen kann, werden die gültigen Werte vor der Summation in einer Menge gesammelt. Am Ende wird über alle verschiedenen progressiven Quadrate summiert.
Sei \(N\) die obere Schranke. Die Anzahl erzeugter Parameter-Tripel ist
$$\sum_{\substack{a\ge 1\\ b<a\\ ab\le \sqrt{N}\\ \gcd(a,b)=1}} \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor,$$
und jedes Tripel verursacht nur konstante Arbeit: einfache Arithmetik, bis zu zwei Quadratwurzeltests und Einfügungen in eine Menge. Das ist erheblich kleiner als alle Zahlen oder alle Quadrate bis \(N\) zu durchsuchen, und für \(N=10^{12}\) problemlos praktikabel.
Als asymptotische Kurzfassung kann man die Enumeration grob als \(O(\sqrt{N}\log^2 N)\) ansehen. Der Speicherverbrauch ist \(O(S)\), wobei \(S\) die Anzahl der verschiedenen gefundenen progressiven Quadrate bezeichnet. In der Praxis ist \(S\) sehr klein, daher bleibt der Speicherbedarf vernachlässigbar.
Progressive sayı, \(n=dq+r\) ve \(0<r<d\) olacak şekilde bir bölen \(d\), bölüm \(q\) ve kalan \(r\) bulunan; ayrıca \(d\), \(q\) ve \(r\) sayıları bir sırada geometrik dizinin ardışık üç terimini oluşturan pozitif tam sayı \(n\)'dir. Problem 141, \(10^{12}\)'yi aşmayan ve aynı zamanda tam kare olan tüm böyle \(n\) değerlerinin toplamını ister.
Zor olan tek bir \(n\)'nin progressive olup olmadığını kontrol etmek değildir; gerçekten mümkün olan adayları üretmektir. Bu yüzden uygulamalar \(10^{12}\)'ye kadar tüm kareleri taramaz. Bunun yerine her uygun geometrik dizi üçlüsünü parametrize eder, bölme özdeşliğini \(n\) için iki açık formüle indirger ve yalnızca bu adayları test eder.
Tüm çözüm, tam sayılardan oluşan ardışık üç geometrik dizi teriminin katı bir biçimde yazılabilmesine dayanır. Bu biçim yazıldıktan sonra \(n=dq+r\) koşulu yalnızca iki farklı cebirsel aile bırakır.
Ortak oranı sadeleştirilmiş biçimde \(a/b>1\) olarak yazalım; burada \(\gcd(a,b)=1\) ve \(a>b\) olsun. En küçük terim \(x\) ise ardışık üç terim
$$x,\quad x\frac{a}{b},\quad x\frac{a^2}{b^2}$$
şeklindedir. Bu üç değerin de tam sayı olması için \(x\)'in \(b^2\)'nin katı olması gerekir. Dolayısıyla \(x=tb^2\) ve \(t\ge 1\) yazabiliriz. Böylece uygun her tam sayı geometrik dizi üçlüsü
$$tb^2,\qquad tab,\qquad ta^2$$
biçimindedir; ayrıca \(a>b\) ve \(\gcd(a,b)=1\) şartları vardır. Uygulamaların \(b<a\) ve aralarında asal \((a,b)\) çiftleri üzerinde dolaşmasının nedeni tam olarak budur: aradıkları şey sadeleştirilmiş ortak oranlardır.
Şimdi bölen \(d\), bölüm \(q\) ve kalan \(r\) bu üç geometrik dizi terimine yerleştirilir. \(0<r<d\) olduğundan kalan en büyük terim olamaz. Böylece cebirsel olarak farklı yalnızca iki durum kalır.
Kalan orta terim ise artan sırada
$$q=tb^2,\qquad r=tab,\qquad d=ta^2$$
olur. Bunu \(n=dq+r\)'de yerine koyarsak
$$n=t^2a^2b^2+tab=tab(tab+1)$$
elde edilir.
Kalan en küçük terim ise \(r=tb^2\) olur ve diğer iki geometrik dizi terimi \(tab\) ile \(ta^2\)'dir. Bunlardan hangisinin bölen, hangisinin bölüm olduğu çarpımı değiştirmediği için
$$n=(tab)(ta^2)+tb^2=t^2a^3b+tb^2=tb(ta^3+b)$$
sonucuna ulaşırız.
Demek ki her progressive sayı şu iki aileden birindedir:
$$\boxed{n_1=tab(tab+1)},\qquad \boxed{n_2=tb(ta^3+b)},$$
burada \(a>b\), \(\gcd(a,b)=1\) ve \(t\ge 1\). C++, Python ve Java uygulamaları tam olarak bu iki formülü üretir, sonra sonucu tam kare olup olmadığına göre filtreler.
\(a=2\), \(b=1\), \(t=1\) alalım. Geometrik dizi terimleri \(1,2,4\) olur.
Kalan en küçük terim seçilirse \(r=1\), \(d=2\), \(q=4\) olur. Bu durumda
$$n=dq+r=2\cdot 4+1=9,$$
ve \(9\) bir tam karedir. Bu en küçük progressive karedir.
Eğer kalan orta terim seçilirse \(q=1\), \(r=2\), \(d=4\) olur. O zaman
$$n=dq+r=4\cdot 1+2=6,$$
elde edilir. Bu sayı progressive'dir ama tam kare değildir. Yani karelik koşulu, progressive adaylar üretildikten sonra ayrıca test edilmelidir.
Her iki ailede de baskın terim en az \(t^2a^2b^2\)'dir. İkinci ailede ayrıca \(a>b\) olduğu için \(t^2a^3b>t^2a^2b^2\) vardır. Dolayısıyla her uygun üçlü
$$t^2a^2b^2\le N$$
eşitsizliğini sağlamak zorundadır; burada \(N=10^{12}\)'dir.
Bu da uygulamalardaki döngü sınırlarını doğrudan verir:
$$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.$$
Bu sınırlar içinde her üçlü en fazla iki aday üretir; biri birinci aileden, diğeri ikinci aileden. \(N\)'yi aşan adaylar anında atılır. \(a>b\) ve \(\gcd(a,b)=1\) koşulları aynı oranı tekrar tekrar yazmayı engellediği için sayım hem eksiksiz hem de gereksiz tekrarlar olmadan yapılır.
C++, Python ve Java uygulamaları önce \(b<a\) olan aralarında asal tüm \((a,b)\) çiftlerini gezer. Sonra \(t^2a^2b^2\le 10^{12}\) sınırını sağlayan tüm ölçek katsayıları \(t\) denenir. Her üçlü için \(n_1\) ve \(n_2\) formülleri hesaplanır. Bu aşama doğrudan matematiksel türetimin kod karşılığıdır; keyfi \(n\) değerleri üzerinde deneme yapılmaz.
Her aday tamsayı karekök testiyle kontrol edilir. Tamsayı kökün karesi tekrar adayın kendisini veriyorsa değer kabul edilir. Aynı kare birden fazla progressive gösterimden çıkabileceği için geçerli değerler toplanmadan önce bir kümede saklanır. Tarama bitince bu farklı progressive karelerin toplamı hesaplanır.
\(N\) üst sınır olsun. Üretilen parametre üçlülerinin sayısı
$$\sum_{\substack{a\ge 1\\ b<a\\ ab\le \sqrt{N}\\ \gcd(a,b)=1}} \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor$$
kadardır ve her üçlü için yapılan iş sabittir: birkaç aritmetik işlem, en fazla iki kare testi ve kümeye ekleme. Bu, \(N\)'ye kadar tüm sayıları ya da tüm kareleri taramaktan çok daha küçüktür ve \(N=10^{12}\) için rahatça uygulanabilir.
Asimptotik olarak bu tarama yaklaşık \(O(\sqrt{N}\log^2 N)\) olarak özetlenebilir. Bellek kullanımı ise bulunan farklı progressive kare sayısı \(S\) için \(O(S)\)'dir. Uygulamada \(S\) çok küçük olduğu için bellek maliyeti ihmal edilebilir düzeydedir.
Un número progresivo es un entero positivo \(n\) para el que existen un divisor \(d\), un cociente \(q\) y un resto \(r\) tales que \(n=dq+r\), \(0<r<d\), y además \(d\), \(q\) y \(r\) son tres términos consecutivos de una progresión geométrica en algún orden. El problema 141 pide sumar todos esos \(n\le 10^{12}\) que también sean cuadrados perfectos.
La dificultad real no está en comprobar un solo \(n\), sino en generar únicamente los valores que pueden funcionar. Por eso las implementaciones no recorren todos los cuadrados hasta \(10^{12}\). En su lugar, parametrizan cada progresión geométrica admisible, convierten la identidad \(n=dq+r\) en dos fórmulas explícitas y solo prueban esos candidatos.
Toda la solución parte de una descripción muy rígida de tres términos enteros consecutivos de una progresión geométrica. Una vez escrita esa forma, la condición \(n=dq+r\) se reduce a solo dos familias algebraicamente distintas.
Escribamos la razón común como \(a/b>1\) en términos reducidos, con \(\gcd(a,b)=1\) y \(a>b\). Si el término más pequeño es \(x\), los tres términos consecutivos son
$$x,\quad x\frac{a}{b},\quad x\frac{a^2}{b^2}.$$
Para que los tres sean enteros, \(x\) debe ser múltiplo de \(b^2\), así que podemos escribir \(x=tb^2\) con \(t\ge 1\). Por lo tanto, toda terna entera admisible de una PG tiene la forma
$$tb^2,\qquad tab,\qquad ta^2,$$
con \(a>b\) y \(\gcd(a,b)=1\). Esa es exactamente la razón por la que las implementaciones recorren pares coprimos \((a,b)\) con \(b<a\): están enumerando razones reducidas, no probando valores al azar.
Ahora colocamos el divisor \(d\), el cociente \(q\) y el resto \(r\) sobre esos tres términos. Como \(0<r<d\), el resto no puede ser el término mayor. Quedan entonces dos posibilidades algebraicamente distintas.
Si el resto es el término intermedio, el orden creciente es
$$q=tb^2,\qquad r=tab,\qquad d=ta^2.$$
Al sustituir en \(n=dq+r\) obtenemos
$$n=t^2a^2b^2+tab=tab(tab+1).$$
Si el resto es el término menor, entonces \(r=tb^2\) y los otros dos términos son \(tab\) y \(ta^2\). Su producto es el mismo sin importar cuál haga de divisor y cuál de cociente, de modo que
$$n=(tab)(ta^2)+tb^2=t^2a^3b+tb^2=tb(ta^3+b).$$
Así, todo número progresivo debe pertenecer a una de las dos familias
$$\boxed{n_1=tab(tab+1)},\qquad \boxed{n_2=tb(ta^3+b)},$$
con \(a>b\), \(\gcd(a,b)=1\) y \(t\ge 1\). Las implementaciones generan exactamente esas dos expresiones y luego verifican si el resultado es un cuadrado perfecto.
Tomemos \(a=2\), \(b=1\), \(t=1\). Los términos de la progresión geométrica son \(1,2,4\).
Si el resto es el término menor, podemos elegir \(r=1\), \(d=2\), \(q=4\). Entonces
$$n=dq+r=2\cdot 4+1=9,$$
y \(9\) es un cuadrado perfecto. Ese es el menor cuadrado progresivo.
Si en cambio el resto es el término intermedio, elegimos \(q=1\), \(r=2\), \(d=4\). Entonces
$$n=dq+r=4\cdot 1+2=6,$$
que sí es progresivo, pero no es cuadrado. El ejemplo deja claro por qué la condición de cuadrado se comprueba aparte, después de generar los candidatos progresivos.
En ambas familias el término dominante es al menos \(t^2a^2b^2\). En la segunda familia incluso se cumple \(t^2a^3b>t^2a^2b^2\), porque \(a>b\). Por lo tanto, cualquier terna admisible debe satisfacer
$$t^2a^2b^2\le N,$$
donde \(N=10^{12}\).
Eso da exactamente los límites de los bucles usados por las implementaciones:
$$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.$$
Dentro de esos límites, cada terna produce como mucho dos candidatos, uno por familia. Cualquier valor que supere \(N\) se descarta de inmediato. Las condiciones \(a>b\) y \(\gcd(a,b)=1\) eliminan descripciones redundantes de la misma razón y mantienen la enumeración completa sin inflarla innecesariamente.
Las implementaciones en C++, Python y Java recorren todos los pares coprimos \((a,b)\) con \(b<a\), y después todos los factores de escala \(t\) compatibles con la cota \(t^2a^2b^2\le 10^{12}\). Para cada terna evalúan las dos fórmulas \(n_1\) y \(n_2\). Es una traducción directa de la derivación matemática; no hay una búsqueda ciega sobre valores arbitrarios de \(n\).
Cada candidato se somete a una prueba de raíz cuadrada entera. Si el cuadrado de la raíz entera coincide exactamente con el candidato, el valor se conserva. Como un mismo cuadrado puede aparecer a partir de más de una descomposición progresiva, los valores válidos se guardan en un conjunto antes de sumarlos. Al final, las implementaciones suman todos los cuadrados progresivos distintos encontrados.
Sea \(N\) la cota superior. El número de ternas de parámetros generadas es
$$\sum_{\substack{a\ge 1\\ b<a\\ ab\le \sqrt{N}\\ \gcd(a,b)=1}} \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor,$$
y cada terna requiere solo trabajo constante: unas pocas operaciones aritméticas, hasta dos pruebas de cuadrado e inserciones en un conjunto. Eso es muchísimo menor que recorrer todos los enteros o todos los cuadrados hasta \(N\), y es totalmente manejable para \(N=10^{12}\).
Como resumen asintótico, la enumeración es aproximadamente \(O(\sqrt{N}\log^2 N)\), mientras que el uso de memoria es \(O(S)\), donde \(S\) es el número de cuadrados progresivos distintos hallados. En la práctica \(S\) es muy pequeño, así que el coste en memoria es despreciable.
如果一个正整数 \(n\) 能写成 \(n=dq+r\)，其中 \(d\) 是除数，\(q\) 是商，\(r\) 是余数，并且满足 \(0<r<d\)，同时 \(d\)、\(q\)、\(r\) 这三个整数按某种顺序恰好是同一等比数列中的连续三项，那么这样的 \(n\) 就称为 progressive number。第 141 题要求求出所有 \(n\le 10^{12}\) 且同时是完全平方数的这类整数之和。
真正困难的地方不是验证某一个给定的 \(n\) 是否 progressive，而是如何只生成那些真正有可能成立的候选值。实现代码并没有把 \(10^{12}\) 以内的所有平方数全部扫描一遍，而是先把所有可能的整数等比三元组参数化，再把 \(n=dq+r\) 化成两个明确的代数公式，最后只检查这些公式产生的候选数。
整个解法建立在一个核心事实之上：由整数构成的连续三个等比项，形状其实非常刚性。一旦把这种形状写出来，题目的除法条件就只会留下两类本质不同的候选表达式。
设公比的既约形式为 \(a/b>1\)，其中 \(\gcd(a,b)=1\) 且 \(a>b\)。如果最小的一项是 \(x\)，那么连续三项就是
$$x,\quad x\frac{a}{b},\quad x\frac{a^2}{b^2}.$$
要让这三项全部都是整数，\(x\) 必须含有足够的 \(b\) 因子，实际上必须是 \(b^2\) 的倍数。所以可以写成 \(x=tb^2\)，其中 \(t\ge 1\) 为整数。于是，任何满足条件的整数等比三元组都可以统一写成
$$tb^2,\qquad tab,\qquad ta^2,$$
并且满足 \(a>b\) 与 \(\gcd(a,b)=1\)。这也正是实现代码要枚举所有互素且满足 \(b<a\) 的 \((a,b)\) 对的原因：它们对应的是所有化到最简后的公比，而不是随意试数。
接下来，把除数 \(d\)、商 \(q\)、余数 \(r\) 放到这三个等比项上。由于 \(0<r<d\)，余数不可能是最大的一项，因此只剩下两种代数上不同的情形。
如果余数是中间那一项，那么递增顺序就是
$$q=tb^2,\qquad r=tab,\qquad d=ta^2.$$
代入 \(n=dq+r\) 得到
$$n=t^2a^2b^2+tab=tab(tab+1).$$
如果余数是最小的一项，那么 \(r=tb^2\)，另外两项是 \(tab\) 和 \(ta^2\)。这两项中谁充当除数、谁充当商都不会改变乘积，因此
$$n=(tab)(ta^2)+tb^2=t^2a^3b+tb^2=tb(ta^3+b).$$
所以，任何 progressive number 都必须落在下面两族之一：
$$\boxed{n_1=tab(tab+1)},\qquad \boxed{n_2=tb(ta^3+b)},$$
其中 \(a>b\)、\(\gcd(a,b)=1\)、\(t\ge 1\)。实现代码正是生成这两种公式对应的值，然后再判断结果是不是完全平方数。
取 \(a=2\)、\(b=1\)、\(t=1\)。这时等比数列三项就是 \(1,2,4\)。
如果余数取最小项，令 \(r=1\)、\(d=2\)、\(q=4\)，那么
$$n=dq+r=2\cdot 4+1=9,$$
而 \(9\) 是完全平方数。这也是最小的 progressive square。
如果改成余数取中间项，令 \(q=1\)、\(r=2\)、\(d=4\)，则
$$n=dq+r=4\cdot 1+2=6.$$
\(6\) 的确是 progressive number，但不是平方数。这个例子说明：等比结构负责生成候选值，而“是否是完全平方”必须作为独立条件再做一次检验，不能从前面的参数化里直接省掉。
对这两类公式来说，主导项至少都是 \(t^2a^2b^2\)。在第二类里，因为 \(a>b\)，甚至有 \(t^2a^3b>t^2a^2b^2\)。因此任何可能的参数三元组都必须满足
$$t^2a^2b^2\le N,$$
这里 \(N=10^{12}\)。
这就直接给出了实现代码中的循环边界：
$$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.$$
在这些范围内，每个 \((a,b,t)\) 最多产生两个候选值，分别来自两类公式。任何超过 \(N\) 的值都会立刻丢弃。条件 \(a>b\) 和 \(\gcd(a,b)=1\) 则保证同一个公比不会被重复描述太多次，因此枚举既完整，又不会出现显而易见的冗余。
C++、Python 和 Java 实现都会先遍历所有满足 \(b<a\) 的互素参数对 \((a,b)\)，再遍历所有满足 \(t^2a^2b^2\le 10^{12}\) 的比例因子 \(t\)。对每个三元组，都计算公式 \(n_1\) 和 \(n_2\)。这一步是数学推导的直接翻译，并不是对任意 \(n\) 做暴力试除或暴力验证。
每个候选值都要经过整数平方根检验。只有当整数平方根的平方恰好等于原候选值时，这个数才会被保留下来。由于同一个平方数可能来自不止一种 progressive 分解方式，所以有效结果会先放入集合中去重，再在最后统一求和。最终返回的就是所有不同 progressive square 的总和。
设上界为 \(N\)。被枚举的参数三元组总数为
$$\sum_{\substack{a\ge 1\\ b<a\\ ab\le \sqrt{N}\\ \gcd(a,b)=1}} \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor,$$
而每个三元组只会触发常数时间的工作：若干次整数运算、至多两次平方检验，以及集合插入。因此，这个方法远小于“遍历所有整数”或者“遍历所有平方数”这两种朴素思路，对 \(N=10^{12}\) 来说完全可行。
如果用渐近记号概括，这种枚举大致可以看作 \(O(\sqrt{N}\log^2 N)\)，而内存消耗是 \(O(S)\)，其中 \(S\) 表示找到的不同 progressive square 的个数。实际运行时 \(S\) 很小，所以内存占用几乎可以忽略。
Прогрессивным называется положительное целое число \(n\), для которого существуют делитель \(d\), частное \(q\) и остаток \(r\) такие, что \(n=dq+r\), \(0<r<d\), а числа \(d\), \(q\) и \(r\) в некотором порядке являются тремя соседними членами геометрической прогрессии. В задаче 141 требуется найти сумму всех таких \(n\le 10^{12}\), которые вдобавок являются полными квадратами.
Трудность здесь не в проверке одного фиксированного \(n\), а в том, чтобы генерировать только действительно возможные кандидаты. Поэтому реализации не перебирают все квадраты до \(10^{12}\). Вместо этого они параметризуют каждую допустимую целочисленную геометрическую прогрессию, превращают условие \(n=dq+r\) в две явные формулы и проверяют только полученные значения.
Вся идея опирается на жесткую форму трех последовательных целых членов геометрической прогрессии. Как только эта форма выписана, условие \(n=dq+r\) сводится всего к двум алгебраически различным семействам.
Пусть общее отношение прогрессии в несократимом виде равно \(a/b>1\), где \(\gcd(a,b)=1\) и \(a>b\). Если наименьший член равен \(x\), то три последовательных члена имеют вид
$$x,\quad x\frac{a}{b},\quad x\frac{a^2}{b^2}.$$
Чтобы все три числа были целыми, \(x\) должен делиться на \(b^2\). Поэтому можно написать \(x=tb^2\), где \(t\ge 1\). Значит, любая допустимая целочисленная тройка членов геометрической прогрессии имеет вид
$$tb^2,\qquad tab,\qquad ta^2,$$
при условиях \(a>b\) и \(\gcd(a,b)=1\). Именно поэтому реализации перебирают взаимно простые пары \((a,b)\) с \(b<a\): они перечисляют все несократимые значения общего отношения.
Теперь нужно распределить делитель \(d\), частное \(q\) и остаток \(r\) по этим трем членам прогрессии. Так как \(0<r<d\), остаток не может быть наибольшим членом. Остаются ровно два алгебраически различных случая.
Если остаток является средним членом, то в возрастающем порядке имеем
$$q=tb^2,\qquad r=tab,\qquad d=ta^2.$$
Подстановка в \(n=dq+r\) дает
$$n=t^2a^2b^2+tab=tab(tab+1).$$
Если же остаток является наименьшим членом, то \(r=tb^2\), а двумя остальными членами служат \(tab\) и \(ta^2\). Какой из них будет делителем, а какой частным, не влияет на произведение, поэтому
$$n=(tab)(ta^2)+tb^2=t^2a^3b+tb^2=tb(ta^3+b).$$
Следовательно, любое progressive number обязательно принадлежит одному из двух семейств
$$\boxed{n_1=tab(tab+1)},\qquad \boxed{n_2=tb(ta^3+b)},$$
где \(a>b\), \(\gcd(a,b)=1\) и \(t\ge 1\). Реализации порождают именно эти две формулы, а затем отдельно проверяют условие полного квадрата.
Возьмем \(a=2\), \(b=1\), \(t=1\). Тогда члены геометрической прогрессии равны \(1,2,4\).
Если остаток — наименьший член, то можно взять \(r=1\), \(d=2\), \(q=4\). Тогда
$$n=dq+r=2\cdot 4+1=9,$$
а \(9\) является полным квадратом. Это наименьший progressive square.
Если же остаток — средний член, то получаем \(q=1\), \(r=2\), \(d=4\). Тогда
$$n=dq+r=4\cdot 1+2=6,$$
то есть число прогрессивное, но не квадрат. Пример показывает, почему условие квадратности нельзя вывести автоматически из параметризации: его нужно проверять отдельно.
В обоих семействах главный вклад не меньше \(t^2a^2b^2\). Во втором семействе даже верно \(t^2a^3b>t^2a^2b^2\), потому что \(a>b\). Значит, любая допустимая тройка параметров обязана удовлетворять неравенству
$$t^2a^2b^2\le N,$$
где \(N=10^{12}\).
Отсюда напрямую следуют границы циклов, использованные в реализациях:
$$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.$$
Внутри этих границ каждая тройка \((a,b,t)\) рождает не более двух кандидатов, по одному из каждого семейства. Значения выше \(N\) сразу отбрасываются. Ограничения \(a>b\) и \(\gcd(a,b)=1\) устраняют лишние описания одного и того же отношения, так что перебор остается полным, но без очевидного дублирования.
Реализации на C++, Python и Java перебирают все взаимно простые пары \((a,b)\) с \(b<a\), а затем все коэффициенты масштаба \(t\), для которых выполняется \(t^2a^2b^2\le 10^{12}\). Для каждой тройки вычисляются формулы \(n_1\) и \(n_2\). Это прямой перенос математического вывода в код; никакого слепого перебора произвольных \(n\) здесь нет.
Каждый кандидат проходит тест целочисленного квадратного корня. Если квадрат найденного целого корня совпадает с исходным числом, кандидат сохраняется. Одно и то же квадратное число может возникать из нескольких progressive-разложений, поэтому корректные значения сначала помещаются в множество, а уже потом суммируются. В конце возвращается сумма всех различных progressive squares.
Пусть \(N\) — верхняя граница. Число перебираемых троек параметров равно
$$\sum_{\substack{a\ge 1\\ b<a\\ ab\le \sqrt{N}\\ \gcd(a,b)=1}} \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor,$$
а на каждую такую тройку приходится только константный объем работы: несколько арифметических операций, не более двух проверок на квадрат и вставки в множество. Это намного меньше, чем перебор всех целых чисел или всех квадратов до \(N\), и для \(N=10^{12}\) работает с большим запасом.
Удобная асимптотическая оценка для такого перебора — примерно \(O(\sqrt{N}\log^2 N)\). Память составляет \(O(S)\), где \(S\) — число различных найденных progressive squares. На практике \(S\) очень мало, поэтому расход памяти несущественен.
يسمى العدد الموجب \(n\) عددًا progressive إذا وُجد قاسم \(d\) وخارج قسمة \(q\) وباقٍ \(r\) بحيث \(n=dq+r\) و \(0<r<d\)، وكانت الأعداد \(d\) و\(q\) و\(r\) تشكل، بترتيب ما، ثلاثة حدود متتالية في متتالية هندسية. يطلب منا السؤال في المسألة 141 إيجاد مجموع كل هذه القيم \(n\le 10^{12}\) التي تكون أيضًا مربعات كاملة.
الصعوبة الحقيقية ليست في اختبار عدد واحد بعينه، بل في توليد القيم التي يمكن أن تنجح أصلًا. لذلك لا تقوم التطبيقات بمسح كل المربعات حتى \(10^{12}\). بدلًا من ذلك، تقوم بتمثيل كل ثلاثية هندسية صحيحة ممكنة على صورة بارامترات، ثم تحوّل العلاقة \(n=dq+r\) إلى صيغتين جبريتين واضحتين، وبعد ذلك تختبر هذه المرشحات فقط.
تعتمد الفكرة كلها على أن ثلاثة حدود صحيحة متتالية في متتالية هندسية لا يمكن أن تأخذ إلا شكلًا محددًا جدًا. وبمجرد كتابة هذا الشكل، ينخفض شرط \(n=dq+r\) إلى عائلتين جبريتين فقط.
لنكتب النسبة المشتركة في أبسط صورة على هيئة \(a/b>1\)، حيث \(\gcd(a,b)=1\) و \(a>b\). إذا كان أصغر حد هو \(x\)، فإن الحدود الثلاثة المتتالية تكون
$$x,\quad x\frac{a}{b},\quad x\frac{a^2}{b^2}.$$
ولكي تكون الحدود الثلاثة كلها أعدادًا صحيحة، يجب أن يكون \(x\) من مضاعفات \(b^2\). لذلك يمكن كتابة \(x=tb^2\) لبعض \(t\ge 1\). وعليه فإن كل ثلاثية صحيحة ممكنة في متتالية هندسية تأخذ الشكل
$$tb^2,\qquad tab,\qquad ta^2,$$
مع الشرطين \(a>b\) و \(\gcd(a,b)=1\). ولهذا السبب بالضبط تمر التطبيقات على الأزواج المتباينة نسبيًا \((a,b)\) مع \(b<a\): فهي تعدّد النسب المختزلة الممكنة، لا أعدادًا عشوائية.
الآن نوزع القاسم \(d\) وخارج القسمة \(q\) والباقي \(r\) على هذه الحدود الثلاثة. وبما أن \(0<r<d\)، فلا يمكن أن يكون الباقي هو الحد الأكبر. وهكذا لا يبقى إلا حالتان مختلفتان جبريًا.
إذا كان الباقي هو الحد الأوسط، فسيكون الترتيب التصاعدي
$$q=tb^2,\qquad r=tab,\qquad d=ta^2.$$
وبالتعويض في \(n=dq+r\) نحصل على
$$n=t^2a^2b^2+tab=tab(tab+1).$$
أما إذا كان الباقي هو الحد الأصغر، فحينئذ \(r=tb^2\)، والحدان الآخران هما \(tab\) و\(ta^2\). ولا يهم أيهما يمثل القاسم وأيهما يمثل خارج القسمة لأن حاصل الضرب واحد في الحالتين، ولذلك
$$n=(tab)(ta^2)+tb^2=t^2a^3b+tb^2=tb(ta^3+b).$$
إذن كل عدد progressive لا بد أن ينتمي إلى إحدى العائلتين
$$\boxed{n_1=tab(tab+1)},\qquad \boxed{n_2=tb(ta^3+b)},$$
حيث \(a>b\) و \(\gcd(a,b)=1\) و \(t\ge 1\). والتطبيقات تولد هاتين الصيغتين بالضبط ثم تختبر بعد ذلك هل الناتج مربع كامل أم لا.
خذ \(a=2\) و\(b=1\) و\(t=1\). عندها تكون حدود المتتالية الهندسية هي \(1,2,4\).
إذا كان الباقي هو الحد الأصغر، نختار \(r=1\) و\(d=2\) و\(q=4\). عندئذ
$$n=dq+r=2\cdot 4+1=9,$$
و\(9\) مربع كامل. وهذا هو أصغر مربع progressive.
أما إذا كان الباقي هو الحد الأوسط، فنأخذ \(q=1\) و\(r=2\) و\(d=4\). وعندها
$$n=dq+r=4\cdot 1+2=6,$$
وهو عدد progressive بالفعل، لكنه ليس مربعًا كاملًا. يوضح هذا المثال لماذا تُفحص خاصية المربع الكامل كاختبار منفصل بعد توليد المرشحات progressive.
في كلتا العائلتين، الحد المسيطر لا يقل عن \(t^2a^2b^2\). وفي العائلة الثانية لدينا أيضًا \(t^2a^3b>t^2a^2b^2\) لأن \(a>b\). لذلك فإن أي ثلاثية صالحة يجب أن تحقق
$$t^2a^2b^2\le N,$$
حيث \(N=10^{12}\).
وهذا يعطينا مباشرة حدود الحلقات المستخدمة في التطبيقات:
$$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.$$
داخل هذه الحدود، تنتج كل ثلاثية \((a,b,t)\) ما يصل إلى مرشحين اثنين، واحد من كل عائلة. وأي قيمة تتجاوز \(N\) تُستبعد فورًا. كما أن الشرطين \(a>b\) و \(\gcd(a,b)=1\) يمنعان الوصف المتكرر للنسبة نفسها، فيبقى التعداد كاملًا من دون تكرار واضح لا حاجة له.
تقوم تطبيقات C++ وPython وJava بالمرور على كل زوج \((a,b)\) متباين نسبيًا مع \(b<a\)، ثم على كل عامل قياس \(t\) يحقق القيد \(t^2a^2b^2\le 10^{12}\). ولكل ثلاثية تحسب الصيغتين \(n_1\) و\(n_2\). هذه الخطوة هي ترجمة مباشرة للاشتقاق الرياضي، وليست بحثًا أعمى في قيم \(n\) العشوائية.
يُختبر كل مرشح باستخدام جذر تربيعي صحيح. فإذا كان مربع الجذر الصحيح يساوي المرشح تمامًا، تُحفظ هذه القيمة. وبما أن المربع نفسه قد يظهر من أكثر من تمثيل progressive واحد، تُخزن القيم المقبولة أولًا في مجموعة لإزالة التكرار قبل جمعها. وفي النهاية تُحسب قيمة المجموع على الأعداد progressive المربعة المميزة فقط.
إذا كان \(N\) هو الحد الأعلى، فإن عدد ثلاثيات البارامترات المولدة يساوي
$$\sum_{\substack{a\ge 1\\ b<a\\ ab\le \sqrt{N}\\ \gcd(a,b)=1}} \left\lfloor \frac{\sqrt{N}}{ab}\right\rfloor,$$
وكل ثلاثية تتطلب عملًا ثابتًا فقط: بعض العمليات الحسابية، وما يصل إلى اختبارين للمربع الكامل، وإدخالات في مجموعة. وهذا أصغر بكثير من فحص جميع الأعداد أو جميع المربعات حتى \(N\)، كما أنه عملي تمامًا عندما يكون \(N=10^{12}\).
ويمكن تلخيص ذلك تقاربيًا بأن التعداد يقع تقريبًا في \(O(\sqrt{N}\log^2 N)\)، بينما استهلاك الذاكرة هو \(O(S)\)، حيث \(S\) عدد المربعات progressive المختلفة التي يتم العثور عليها. وعمليًا تكون \(S\) صغيرة جدًا، لذا تبقى كلفة الذاكرة ضئيلة.