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.
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.
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\).
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)\).
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)\).
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.
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\).
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.
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.
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\).
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.
Eine positive ganze Zahl \(k\) heißt square-pivot, wenn es ganze Zahlen \(m>0\) und \(n\ge k\) gibt mit
$$ (k-m)^2+(k-m+1)^2+\cdots+k^2=(n+1)^2+(n+2)^2+\cdots+(n+m)^2. $$
Also muss die Summe der \((m+1)\) aufeinanderfolgenden Quadrate bis \(k\) gleich der Summe der \(m\) aufeinanderfolgenden Quadrate direkt nach \(n\) sein.
Gesucht ist die Summe aller verschiedenen square-pivots
$$ k\le L, $$
wobei im eigentlichen Problem \(L=10^{10}\) ist. Der Code durchsucht nicht naiv alle Tripel \((k,m,n)\), sondern reduziert die Bedingung auf Pell-Gleichungen.
Ausgehend von
$$ \sum_{i=0}^{m}(k-i)^2=\sum_{j=1}^{m}(n+j)^2 $$
liefert die Summenformel für Quadrate links
$$ (m+1)k^2-km(m+1)+\frac{m(m+1)(2m+1)}{6}, $$
und rechts
$$ mn^2+m(m+1)n+\frac{m(m+1)(2m+1)}{6}. $$
Der gemeinsame kubische Term kürzt sich weg. Übrig bleibt die Schlüsselformel
$$ (m+1)k(k-m)=m\,n(n+m+1). $$
Für festes \(k\) und \(m\) ist das eine quadratische Gleichung in \(n\):
$$ n^2+(m+1)n-\frac{(m+1)k(k-m)}{m}=0. $$
Daher ist \(n\) genau dann ganzzahlig, wenn die Diskriminante
$$ \Delta=(m+1)^2+4\frac{(m+1)k(k-m)}{m} $$
ein perfektes Quadrat ist und die Parität passt.
Genau das prüft die Checkpoint-Funktion brute_pivots.
Setze
$$ A=2n+m+1,\qquad B=2k-m. $$
Dann gilt
$$ n(n+m+1)=\frac{A^2-(m+1)^2}{4},\qquad k(k-m)=\frac{B^2-m^2}{4}. $$
Damit wird die Gleichung zu
$$ mA^2-(m+1)B^2=m(m+1). $$
Schreibe
$$ m(m+1)=s q^2, $$
wobei \(s\) quadratfrei ist.
Nun verwende die lineare Substitution
$$ A=(m+1)x+qsy,\qquad B=mx+qsy. $$
Ein direktes Ausmultiplizieren liefert
$$ mA^2-(m+1)B^2=s q^2(x^2-sy^2). $$
Da die linke Seite gleich \(m(m+1)=s q^2\) sein muss, folgt nach Kürzen die Pell-Gleichung
$$ x^2-sy^2=1. $$
Aus \(B=2k-m\) und \(A=2n+m+1\) folgt
$$ k=\frac{mx+qsy+m}{2}, $$
$$ n=\frac{(m+1)x+qsy-(m+1)}{2}. $$
Außerdem ist
$$ x=A-B=2(n-k+m)+1. $$
Deshalb gelten genau die im Code auftauchenden Filter:
1. \(x\) muss ungerade sein,
2. \(n\ge k\) ist äquivalent zu \(x\ge 2m+1\),
3. der Zähler in der Formel für \(k\) muss gerade sein.
Für \(m=1\) ist
$$ m(m+1)=2=2\cdot 1^2, $$
also \(s=2\), \(q=1\) und die Pell-Gleichung lautet
$$ x^2-2y^2=1. $$
Die Lösung \((3,2)\) liefert \(k=4\), die nächste Lösung \((17,12)\) liefert \(k=21\).
Für \(m=3\) hat man \(12=3\cdot 2^2\), also \(s=3\), \(q=2\), und \((x,y)=(7,4)\) ergibt \(k=24\).
Für \(m=2\) hat man \(6=6\cdot 1^2\), also \(s=6\), \(q=1\), und \((49,20)\) ergibt \(k=110\).
Aus \(n\ge k\) folgt
$$ n(n+m+1)\ge k(k+m+1). $$
Zusammen mit
$$ (m+1)k(k-m)=m\,n(n+m+1) $$
ergibt das
$$ k\ge 2m(m+1). $$
Also muss bei \(k\le L\) gelten
$$ 2m(m+1)\le L, $$
und damit
$$ m\le \left\lfloor\frac{\sqrt{2L+1}-1}{2}\right\rfloor. $$
Außerdem gilt wegen
$$ k=\frac{mx+qsy+m}{2}\ge \frac{mx+m}{2} $$
die sichere Obergrenze
$$ x\le \frac{2L-m}{m}. $$
Viele verschiedene \(m\) besitzen denselben quadratfreien Anteil \(s\) in der Zerlegung von \(m(m+1)\).
Da die Pell-Gleichung nur von \(s\) abhängt, löst der Code das Pell-Problem einmal pro Gruppe und verwendet dieselbe Lösungsfolge für alle Einträge dieser Gruppe wieder.
Verschiedene \((m,n)\)-Paare können sogar denselben Pivot \(k\) erzeugen. Zum Beispiel entsteht
$$ 684 $$
sowohl aus \((m,n)=(4,760)\) als auch aus \((18,684)\). Deshalb ist globale Deduplikation nötig.
build_primes erzeugt eine Primliste. squarefree_and_square_part schreibt Zahlen in der Form \(s q^2\) mit quadratfreiem \(s\).
Für jedes zulässige \(m\) berechnet der Code \(m(m+1)\), extrahiert \(s\) und \(q\), bestimmt die sichere Grenze x_max und speichert \((m,q,x_{\max})\) in einer Hash-Tabelle nach \(s\) gruppiert.
find_fundamental_pell_limited benutzt Kettenbrüche für die Fundamentallösung, und pell_solutions_up_to erzeugt alle weiteren Lösungen über die übliche Pell-Rekursion.
Danach werden die Kandidaten
$$ k=\frac{mx+qsy+m}{2} $$
zurückgerechnet, gefiltert, gesammelt, sortiert und dedupliziert. Die Checkpoints vergleichen schnell gegen brute force bis \(5000\) und prüfen die Beispiel-Pivots \(4,21,24,110\) unter \(120\).
Der Bereich für \(m\) ist nur von Größe \(O(\sqrt{L})\), und jedes \(m\) wird genau einmal faktorisiert.
Die Hauptarbeit steckt danach in der Pell-Erzeugung pro quadratfreier Klasse \(s\) sowie in der Rückprojektion dieser Lösungen auf die Kandidaten \(k\).
Der Speicher wird im Wesentlichen bestimmt durch:
1. die Gruppierung nach \(s\),
2. die temporären Pell-Lösungen einer Gruppe,
3. den Vektor der verschiedenen Pivotwerte.
Pozitif bir \(k\) tamsayısına square-pivot denir, eğer \(m>0\) ve \(n\ge k\) olacak şekilde
$$ (k-m)^2+(k-m+1)^2+\cdots+k^2=(n+1)^2+(n+2)^2+\cdots+(n+m)^2 $$
eşitliği sağlanıyorsa.
Yani \(k\) ile biten \((m+1)\) ardışık karenin toplamı, \(n\)'den hemen sonra başlayan \(m\) ardışık karenin toplamına eşit olmalıdır.
İstenen şey,
$$ k\le L $$
koşulunu sağlayan tüm farklı square-pivot değerlerinin toplamıdır. Gerçek problemde \(L=10^{10}\) alınır. Kod bunu \((k,m,n)\) üzerinde kaba kuvvet taramasıyla değil, Pell denklemlerine indirgeme ile çözer.
Başlangıç eşitliği
$$ \sum_{i=0}^{m}(k-i)^2=\sum_{j=1}^{m}(n+j)^2 $$
olsun.
Kare toplamı formülü kullanılırsa sol taraf
$$ (m+1)k^2-km(m+1)+\frac{m(m+1)(2m+1)}{6}, $$
sağ taraf ise
$$ mn^2+m(m+1)n+\frac{m(m+1)(2m+1)}{6} $$
olur.
Ortak kübik kuyruk sadeleşince temel Diofant eşitliği kalır:
$$ (m+1)k(k-m)=m\,n(n+m+1). $$
Sabit \(k\) ve \(m\) için bu eşitlik, \(n\) açısından ikinci derecedir:
$$ n^2+(m+1)n-\frac{(m+1)k(k-m)}{m}=0. $$
Dolayısıyla \(n\)'in tam sayı olması için diskriminantın
$$ \Delta=(m+1)^2+4\frac{(m+1)k(k-m)}{m} $$
tam kare olması ve paritenin uyması gerekir.
Koddaki brute_pivots fonksiyonu tam olarak bunu yapar: küçük limitlerde \(k\) ve \(m\) üzerinden dolaşır, diskriminantı hesaplar, kare olup olmadığını kontrol eder ve ardından \(n\)'i geri kurar.
Şu kaydırılmış değişkenleri tanımlayalım:
$$ A=2n+m+1,\qquad B=2k-m. $$
O zaman
$$ n(n+m+1)=\frac{A^2-(m+1)^2}{4}, $$
ve
$$ k(k-m)=\frac{B^2-m^2}{4}. $$
Bunları yerine koyunca denklem şu hale gelir:
$$ mA^2-(m+1)B^2=m(m+1). $$
Bu biçim Pell indirgemesine çok daha yakındır.
Şimdi
$$ m(m+1)=s q^2 $$
yazalım; burada \(s\) squarefree, \(q\) ise kare kısmıdır.
Ardından şu lineer dönüşümü yapalım:
$$ A=(m+1)x+qsy,\qquad B=mx+qsy. $$
Doğrudan açılım
$$ mA^2-(m+1)B^2=s q^2(x^2-sy^2) $$
verir.
Sol tarafın \(m(m+1)=s q^2\) olması gerektiğinden sadeleştirme sonrası Pell denklemi elde edilir:
$$ x^2-sy^2=1. $$
Yani sabit bir \(m\) için uygun pivotlar, \(m(m+1)\)'in squarefree kısmına bağlı Pell çözümlerinden gelir.
\(B=2k-m\) ve \(A=2n+m+1\) olduğuna göre ters dönüşüm
$$ k=\frac{mx+qsy+m}{2}, $$
$$ n=\frac{(m+1)x+qsy-(m+1)}{2} $$
şeklindedir.
Ayrıca
$$ x=A-B=2(n-k+m)+1 $$
olur.
Bu eşitlik, koddaki üç filtrenin nedenini doğrudan açıklar:
1. \(x\) tek olmalıdır,
2. \(n\ge k\) koşulu \(x\ge 2m+1\) ile aynıdır,
3. \(k\) formülündeki pay çift olmalıdır.
\(m=1\) için
$$ m(m+1)=2=2\cdot 1^2 $$
olur; yani \(s=2\), \(q=1\). Pell denklemi
$$ x^2-2y^2=1 $$
şeklindedir.
\((x,y)=(3,2)\) çözümü
$$ k=\frac{3+4+1}{2}=4,\qquad n=\frac{6+4-2}{2}=4 $$
verir.
Bir sonraki çözüm \((17,12)\) ise
$$ k=\frac{17+24+1}{2}=21,\qquad n=\frac{34+24-2}{2}=28 $$
sonucunu verir.
\(m=3\) için \(12=3\cdot 2^2\), yani \(s=3\), \(q=2\). \((x,y)=(7,4)\) çözümü
$$ k=\frac{3\cdot 7+2\cdot 3\cdot 4+3}{2}=24 $$
üretir.
\(m=2\) için \(s=6\), \(q=1\) ve \((49,20)\) çözümü
$$ k=\frac{2\cdot 49+6\cdot 20+2}{2}=110 $$
verir. Böylece resmi örnekler \(4\), \(21\), \(24\) ve \(110\) geri elde edilir.
İmplementasyon \(m\) değerini sonsuza kadar götürmez.
\(n\ge k\) olduğundan
$$ n(n+m+1)\ge k(k+m+1) $$
vardır.
Bunu
$$ (m+1)k(k-m)=m\,n(n+m+1) $$
ile birleştirince
$$ k\ge 2m(m+1) $$
çıkar.
Dolayısıyla \(k\le L\) ise mutlaka
$$ 2m(m+1)\le L $$
olmalıdır. Bu da kodun kullandığı
$$ m\le \left\lfloor\frac{\sqrt{2L+1}-1}{2}\right\rfloor $$
sınırını verir.
Ayrıca
$$ k=\frac{mx+qsy+m}{2}\ge \frac{mx+m}{2} $$
olduğundan \(k\le L\) için
$$ x\le \frac{2L-m}{m} $$
gerekir. Bu yüzden her giriş için x_max saklanır.
Farklı \(m\) değerleri, \(m(m+1)\) ayrışımında aynı squarefree \(s\) kısmını paylaşabilir.
Pell denklemi sadece \(s\)'ye bağlı olduğu için kod, aynı \(s\)'ye sahip tüm \(m\) değerlerini gruplar; ilgili Pell akışını bir kez üretip grubun tüm üyeleri için tekrar kullanır.
Bu, her \(m\) için ayrı Pell çözmekten çok daha verimlidir.
Üstelik farklı \((m,n)\) çiftleri aynı pivot \(k\)'yı da üretebilir. Örneğin
$$ 684 $$
hem \((m,n)=(4,760)\) hem de \((18,684)\) ile ortaya çıkar. Bu yüzden finalde global tekilleştirme zorunludur.
build_primes asal listesini üretir. squarefree_and_square_part, sayıyı squarefree kısım \(s\) ve kare kısım \(q\) olarak ayırır.
Her uygun \(m\) için kod, \(m(m+1)\)'i hesaplar, \(s\) ve \(q\)'yu çıkarır, güvenli \(x\)-üst sınırı olan x_max'i bulur ve \((m,q,x_{\max})\) bilgisini \(s\) anahtarıyla bir hash tabloda toplar.
find_fundamental_pell_limited sürekli kesirlerle temel Pell çözümünü bulur; pell_solutions_up_to ise standart Pell özyinelemesiyle tüm sonraki çözümleri üretir:
$$ x_{t+1}=x_1x_t+s y_1y_t,\qquad y_{t+1}=x_1y_t+y_1x_t. $$
Sonra her grup için
$$ k=\frac{mx+qsy+m}{2} $$
formülüyle adaylar üretilir; tek/çiftlik, alt sınır, parite ve \(k\le L\) kontrolleri uygulanır. En sonda adaylar sıralanır, tekilleştirilir ve toplanır.
Checkpoint tarafında hızlı yöntem \(5000\)'e kadar brute force ile karşılaştırılır ve \(120\) altında \(4,21,24,110\) örnekleri aranır.
\(m\) aralığı yalnızca \(O(\sqrt{L})\) boyutundadır ve her \(m\) yalnızca bir kez çarpanlarına ayrılır.
Asıl maliyet, farklı squarefree sınıflar \(s\) için Pell çözümlerini üretmek ve bunları grup üyeleri için aday pivotlara geri çevirmektir.
Bellek kullanımı başlıca üç yerde yoğunlaşır:
1. \(s\)'ye göre gruplama tablosu,
2. tek bir grup için geçici Pell çözüm listesi,
3. farklı pivot değerlerinin tutulduğu final vektörü.
Yani esas fikir bütün problem için kapalı form bulmak değil; üç parametreli \((k,m,n)\) aramasını, squarefree sınıflarla indekslenmiş yeniden kullanılabilir Pell akışlarına indirmektir.
Un entero positivo \(k\) se llama square-pivot si existen enteros \(m>0\) y \(n\ge k\) tales que
$$ (k-m)^2+(k-m+1)^2+\cdots+k^2=(n+1)^2+(n+2)^2+\cdots+(n+m)^2. $$
Es decir, la suma de los \((m+1)\) cuadrados consecutivos que terminan en \(k\) debe coincidir con la suma de los \(m\) cuadrados consecutivos que empiezan justo después de \(n\).
Se pide sumar todos los square-pivots distintos con
$$ k\le L. $$
En el problema completo \(L=10^{10}\). El código no recorre ingenuamente todos los triples \((k,m,n)\); en su lugar, transforma la condición en un problema de Pell.
Partimos de
$$ \sum_{i=0}^{m}(k-i)^2=\sum_{j=1}^{m}(n+j)^2. $$
La suma de la izquierda vale
$$ (m+1)k^2-km(m+1)+\frac{m(m+1)(2m+1)}{6}, $$
y la de la derecha
$$ mn^2+m(m+1)n+\frac{m(m+1)(2m+1)}{6}. $$
Al cancelar el término común aparece la identidad central
$$ (m+1)k(k-m)=m\,n(n+m+1). $$
Para \(k\) y \(m\) fijos, esto es una ecuación cuadrática en \(n\):
$$ n^2+(m+1)n-\frac{(m+1)k(k-m)}{m}=0. $$
Por tanto, \(n\) es entero exactamente cuando el discriminante
$$ \Delta=(m+1)^2+4\frac{(m+1)k(k-m)}{m} $$
es un cuadrado perfecto y la paridad es correcta.
Eso es precisamente lo que hace brute_pivots en los checkpoints.
Definimos
$$ A=2n+m+1,\qquad B=2k-m. $$
Entonces
$$ n(n+m+1)=\frac{A^2-(m+1)^2}{4},\qquad k(k-m)=\frac{B^2-m^2}{4}. $$
La ecuación se convierte en
$$ mA^2-(m+1)B^2=m(m+1). $$
Escribimos
$$ m(m+1)=s q^2, $$
con \(s\) squarefree.
Hacemos el cambio lineal
$$ A=(m+1)x+qsy,\qquad B=mx+qsy. $$
Al expandir se obtiene
$$ mA^2-(m+1)B^2=s q^2(x^2-sy^2). $$
Como el lado izquierdo debe ser \(m(m+1)=s q^2\), queda la ecuación de Pell
$$ x^2-sy^2=1. $$
Las fórmulas inversas son
$$ k=\frac{mx+qsy+m}{2}, $$
$$ n=\frac{(m+1)x+qsy-(m+1)}{2}. $$
Además,
$$ x=A-B=2(n-k+m)+1. $$
De aquí salen exactamente los filtros del código:
1. \(x\) debe ser impar,
2. \(n\ge k\) equivale a \(x\ge 2m+1\),
3. el numerador de la fórmula de \(k\) debe ser par.
Para \(m=1\), se tiene \(m(m+1)=2\), así que \(s=2\), \(q=1\), y la Pell correspondiente es
$$ x^2-2y^2=1. $$
La solución \((3,2)\) produce \(k=4\); la siguiente \((17,12)\) produce \(k=21\).
Para \(m=3\), \(12=3\cdot 2^2\), luego \(s=3\), \(q=2\), y \((7,4)\) produce \(k=24\).
Para \(m=2\), \(s=6\), \(q=1\), y \((49,20)\) produce \(k=110\).
Como \(n\ge k\), se cumple
$$ n(n+m+1)\ge k(k+m+1). $$
Combinando con
$$ (m+1)k(k-m)=m\,n(n+m+1) $$
se obtiene
$$ k\ge 2m(m+1). $$
Por tanto, si \(k\le L\), necesariamente
$$ 2m(m+1)\le L, $$
de donde sale
$$ m\le \left\lfloor\frac{\sqrt{2L+1}-1}{2}\right\rfloor. $$
Además, de
$$ k=\frac{mx+qsy+m}{2}\ge \frac{mx+m}{2} $$
se deduce
$$ x\le \frac{2L-m}{m}, $$
que es justamente el x_max almacenado en cada entrada.
Muchos valores de \(m\) comparten la misma parte squarefree \(s\) en la factorización de \(m(m+1)\).
Como la ecuación de Pell depende solo de \(s\), el programa la resuelve una sola vez por grupo y reutiliza esa secuencia de soluciones para todos los \(m\) del grupo.
Incluso distintos pares \((m,n)\) pueden producir el mismo pivot \(k\). Por ejemplo,
$$ 684 $$
aparece tanto con \((m,n)=(4,760)\) como con \((18,684)\), así que la deduplicación global es obligatoria.
build_primes genera apoyo primo para factorizar. squarefree_and_square_part escribe un número en la forma \(s q^2\).
Para cada \(m\) admisible, el código calcula \(m(m+1)\), extrae \(s\) y \(q\), calcula x_max y guarda \((m,q,x_{\max})\) en un mapa hash indexado por \(s\).
find_fundamental_pell_limited usa fracciones continuas para hallar la solución fundamental de Pell, y pell_solutions_up_to genera las siguientes mediante la recurrencia estándar.
Después convierte cada solución en un candidato
$$ k=\frac{mx+qsy+m}{2}, $$
aplica filtros de imparidad, cota inferior, paridad e intervalo, reúne todos los candidatos, los ordena, elimina duplicados y los suma.
El rango de \(m\) es solo \(O(\sqrt{L})\), y cada \(m\) se factoriza una vez.
El coste dominante proviene de generar soluciones de Pell para cada clase squarefree \(s\) y proyectarlas sobre los distintos \(m\) del grupo.
La memoria está dominada por:
1. la tabla de agrupación por \(s\),
2. la lista temporal de soluciones de Pell de un grupo,
3. el vector final de pivotes distintos.
如果存在整数 \(m>0\) 与 \(n\ge k\)，使得
$$ (k-m)^2+(k-m+1)^2+\cdots+k^2=(n+1)^2+(n+2)^2+\cdots+(n+m)^2, $$
那么正整数 \(k\) 就叫做 square-pivot。
也就是说，以 \(k\) 结尾的 \((m+1)\) 个连续平方之和，要等于从 \(n+1\) 开始的 \(m\) 个连续平方之和。
题目要求求出所有不同的 square-pivot，满足
$$ k\le L. $$
完整题目中 \(L=10^{10}\)。程序并不直接暴力枚举 \((k,m,n)\)，而是把条件转成 Pell 方程流程。
从
$$ \sum_{i=0}^{m}(k-i)^2=\sum_{j=1}^{m}(n+j)^2 $$
出发。
左边可化为
$$ (m+1)k^2-km(m+1)+\frac{m(m+1)(2m+1)}{6}, $$
右边可化为
$$ mn^2+m(m+1)n+\frac{m(m+1)(2m+1)}{6}. $$
公共项约掉之后，得到核心等式
$$ (m+1)k(k-m)=m\,n(n+m+1). $$
固定 \(k,m\) 时，它是关于 \(n\) 的二次方程：
$$ n^2+(m+1)n-\frac{(m+1)k(k-m)}{m}=0. $$
因此 \(n\) 为整数，当且仅当判别式
$$ \Delta=(m+1)^2+4\frac{(m+1)k(k-m)}{m} $$
是完全平方，并且奇偶性正确。
这正是 brute_pivots 在小范围里做的事。
令
$$ A=2n+m+1,\qquad B=2k-m. $$
则
$$ n(n+m+1)=\frac{A^2-(m+1)^2}{4},\qquad k(k-m)=\frac{B^2-m^2}{4}. $$
原式变成
$$ mA^2-(m+1)B^2=m(m+1). $$
把
$$ m(m+1)=s q^2 $$
写成 squarefree 部分 \(s\) 乘平方部分 \(q^2\)。
再作线性替换
$$ A=(m+1)x+qsy,\qquad B=mx+qsy. $$
直接展开可得
$$ mA^2-(m+1)B^2=s q^2(x^2-sy^2). $$
由于左边必须等于 \(m(m+1)=s q^2\)，约去之后便得到 Pell 方程
$$ x^2-sy^2=1. $$
逆变换公式为
$$ k=\frac{mx+qsy+m}{2}, $$
$$ n=\frac{(m+1)x+qsy-(m+1)}{2}. $$
并且
$$ x=A-B=2(n-k+m)+1. $$
这就解释了代码中的三个过滤条件：
1. \(x\) 必须是奇数，
2. \(n\ge k\) 等价于 \(x\ge 2m+1\)，
3. 求 \(k\) 时分子必须为偶数。
\(m=1\) 时，\(m(m+1)=2\)，所以 \(s=2\)，\(q=1\)，对应 Pell 方程
$$ x^2-2y^2=1. $$
\((x,y)=(3,2)\) 给出 \(k=4\)，下一组 \((17,12)\) 给出 \(k=21\)。
\(m=3\) 时，\(12=3\cdot 2^2\)，所以 \(s=3\)，\(q=2\)，\((7,4)\) 给出 \(k=24\)。
\(m=2\) 时，\(s=6\)，\(q=1\)，\((49,20)\) 给出 \(k=110\)。
因为 \(n\ge k\)，所以
$$ n(n+m+1)\ge k(k+m+1). $$
再结合
$$ (m+1)k(k-m)=m\,n(n+m+1) $$
可推出
$$ k\ge 2m(m+1). $$
因此当 \(k\le L\) 时，必有
$$ 2m(m+1)\le L, $$
也就是
$$ m\le \left\lfloor\frac{\sqrt{2L+1}-1}{2}\right\rfloor. $$
另外，由于
$$ k=\frac{mx+qsy+m}{2}\ge \frac{mx+m}{2}, $$
所以还有
$$ x\le \frac{2L-m}{m}, $$
这就是每条记录保存的 x_max。
不同的 \(m\) 往往会产生相同的 squarefree 部分 \(s\)。
由于 Pell 方程只依赖于 \(s\)，程序只需对每个 \(s\) 求一次 Pell 解流，再把这一整条解流复用给组内所有 \(m\)。
甚至不同的 \((m,n)\) 还可能对应同一个 pivot \(k\)。例如
$$ 684 $$
既可以由 \((m,n)=(4,760)\) 产生，也可以由 \((18,684)\) 产生，所以最终必须全局去重。
build_primes 负责提供素数支持，squarefree_and_square_part 把整数写成 \(s q^2\) 的形式。
对每个允许的 \(m\)，代码计算 \(m(m+1)\)，提取 \(s\) 与 \(q\)，求出安全上界 x_max，并把 \((m,q,x_{\max})\) 存到以 \(s\) 为键的分组表中。
find_fundamental_pell_limited 通过连分数寻找 Pell 基本解，pell_solutions_up_to 再用标准递推生成后续解。
之后程序用
$$ k=\frac{mx+qsy+m}{2} $$
把每个 Pell 解映射回候选 pivot，再施加奇偶、下界、整除和范围过滤，最终排序、去重并求和。
\(m\) 的搜索范围只有 \(O(\sqrt{L})\) 大小，而且每个 \(m\) 只分解一次。
主要开销来自对每个不同的 squarefree 类 \(s\) 生成 Pell 解，并把这些解投影回组内各个 \(m\) 的候选 \(k\)。
内存主要花在：
1. 按 \(s\) 分组的表，
2. 单个分组的临时 Pell 解列表，
3. 最终不同 pivot 的向量。
Положительное целое \(k\) называется square-pivot, если существуют целые \(m>0\) и \(n\ge k\), для которых
$$ (k-m)^2+(k-m+1)^2+\cdots+k^2=(n+1)^2+(n+2)^2+\cdots+(n+m)^2. $$
То есть сумма \((m+1)\) последовательных квадратов, оканчивающихся в \(k\), должна совпадать с суммой \(m\) последовательных квадратов, начинающихся сразу после \(n\).
Нужно найти сумму всех различных square-pivot со свойством
$$ k\le L. $$
В полной задаче \(L=10^{10}\). Решение не перебирает все тройки \((k,m,n)\), а сводит задачу к уравнениям Пелля.
Начинаем с
$$ \sum_{i=0}^{m}(k-i)^2=\sum_{j=1}^{m}(n+j)^2. $$
Левая часть равна
$$ (m+1)k^2-km(m+1)+\frac{m(m+1)(2m+1)}{6}, $$
а правая часть равна
$$ mn^2+m(m+1)n+\frac{m(m+1)(2m+1)}{6}. $$
Общий кубический хвост сокращается, и остается ключевое диофантово условие
$$ (m+1)k(k-m)=m\,n(n+m+1). $$
При фиксированных \(k\) и \(m\) это квадратное уравнение по \(n\):
$$ n^2+(m+1)n-\frac{(m+1)k(k-m)}{m}=0. $$
Значит, \(n\) является целым тогда и только тогда, когда дискриминант
$$ \Delta=(m+1)^2+4\frac{(m+1)k(k-m)}{m} $$
является точным квадратом и совпадает по четности.
Именно это делает функция brute_pivots в checkpoint-проверке.
Введем переменные
$$ A=2n+m+1,\qquad B=2k-m. $$
Тогда
$$ n(n+m+1)=\frac{A^2-(m+1)^2}{4},\qquad k(k-m)=\frac{B^2-m^2}{4}. $$
И исходное условие переписывается как
$$ mA^2-(m+1)B^2=m(m+1). $$
Пишем
$$ m(m+1)=s q^2, $$
где \(s\) квадратсвободно.
Далее делаем линейную замену
$$ A=(m+1)x+qsy,\qquad B=mx+qsy. $$
После раскрытия скобок получается
$$ mA^2-(m+1)B^2=s q^2(x^2-sy^2). $$
Так как левая часть должна равняться \(m(m+1)=s q^2\), получаем уравнение Пелля
$$ x^2-sy^2=1. $$
Обратные формулы таковы:
$$ k=\frac{mx+qsy+m}{2}, $$
$$ n=\frac{(m+1)x+qsy-(m+1)}{2}. $$
Кроме того,
$$ x=A-B=2(n-k+m)+1. $$
Отсюда сразу видны фильтры в коде:
1. \(x\) должен быть нечетным,
2. условие \(n\ge k\) эквивалентно \(x\ge 2m+1\),
3. числитель формулы для \(k\) должен быть четным.
При \(m=1\) имеем \(m(m+1)=2\), то есть \(s=2\), \(q=1\), и уравнение Пелля
$$ x^2-2y^2=1. $$
Решение \((3,2)\) дает \(k=4\), а следующее решение \((17,12)\) дает \(k=21\).
При \(m=3\) имеем \(12=3\cdot 2^2\), значит \(s=3\), \(q=2\), и \((7,4)\) дает \(k=24\).
При \(m=2\) имеем \(s=6\), \(q=1\), и \((49,20)\) дает \(k=110\).
Из \(n\ge k\) следует
$$ n(n+m+1)\ge k(k+m+1). $$
Совмещая это с
$$ (m+1)k(k-m)=m\,n(n+m+1), $$
получаем
$$ k\ge 2m(m+1). $$
Следовательно, при \(k\le L\) обязательно
$$ 2m(m+1)\le L, $$
то есть
$$ m\le \left\lfloor\frac{\sqrt{2L+1}-1}{2}\right\rfloor. $$
Кроме того, из
$$ k=\frac{mx+qsy+m}{2}\ge \frac{mx+m}{2} $$
получаем верхнюю оценку
$$ x\le \frac{2L-m}{m}, $$
и именно она хранится в x_max.
Разные значения \(m\) могут иметь один и тот же квадратсвободный множитель \(s\) в разложении \(m(m+1)\).
Поскольку уравнение Пелля зависит только от \(s\), код решает его один раз на группу и затем использует одну и ту же последовательность решений для всех \(m\) из этой группы.
При этом разные пары \((m,n)\) могут давать один и тот же pivot \(k\). Например,
$$ 684 $$
получается и из \((m,n)=(4,760)\), и из \((18,684)\), поэтому финальная глобальная дедупликация обязательна.
build_primes создает список простых чисел. squarefree_and_square_part раскладывает число в виде \(s q^2\).
Для каждого допустимого \(m\) код вычисляет \(m(m+1)\), извлекает \(s\) и \(q\), находит безопасную границу x_max и сохраняет \((m,q,x_{\max})\) в хеш-таблице, индексированной по \(s\).
find_fundamental_pell_limited использует цепные дроби для фундаментального решения Пелля, а pell_solutions_up_to порождает все последующие решения стандартной рекурсией.
Затем каждое решение отображается обратно в кандидат
$$ k=\frac{mx+qsy+m}{2}, $$
после чего применяются проверки на нечетность, нижнюю границу, четность числителя и условие \(k\le L\). Все подходящие значения сортируются, очищаются от дублей и суммируются.
Диапазон \(m\) имеет размер только \(O(\sqrt{L})\), и каждое \(m\) факторизуется один раз.
Основная трудоемкость связана с генерацией решений Пелля для каждого квадратсвободного класса \(s\) и отображением этих решений обратно в кандидаты \(k\).
Память в основном расходуется на:
1. таблицу группировки по \(s\),
2. временный список решений Пелля для одной группы,
3. итоговый вектор различных pivot-значений.
يُسمى العدد الصحيح الموجب \(k\) square-pivot إذا وُجد عددان صحيحان \(m>0\) و\(n\ge k\) بحيث
$$ (k-m)^2+(k-m+1)^2+\cdots+k^2=(n+1)^2+(n+2)^2+\cdots+(n+m)^2. $$
أي إن مجموع \((m+1)\) من المربعات المتتالية المنتهية عند \(k\) يجب أن يساوي مجموع \(m\) من المربعات المتتالية التي تبدأ مباشرة بعد \(n\).
المطلوب هو جمع جميع قيم square-pivot المختلفة التي تحقق
$$ k\le L. $$
وفي المسألة الأصلية يكون \(L=10^{10}\). لا يقوم الكود بفحص جميع الثلاثيات \((k,m,n)\) مباشرة، بل يحول الشرط إلى مسار يعتمد على معادلات Pell.
نبدأ من
$$ \sum_{i=0}^{m}(k-i)^2=\sum_{j=1}^{m}(n+j)^2. $$
ويصبح الطرف الأيسر
$$ (m+1)k^2-km(m+1)+\frac{m(m+1)(2m+1)}{6}, $$
بينما يصبح الطرف الأيمن
$$ mn^2+m(m+1)n+\frac{m(m+1)(2m+1)}{6}. $$
بعد حذف الحد المشترك نحصل على العلاقة الديوفانتية الأساسية
$$ (m+1)k(k-m)=m\,n(n+m+1). $$
إذا ثبتنا \(k\) و\(m\)، أصبحت المعادلة تربيعية في \(n\):
$$ n^2+(m+1)n-\frac{(m+1)k(k-m)}{m}=0. $$
ولذلك يكون \(n\) عددًا صحيحًا إذا وفقط إذا كان المميز
$$ \Delta=(m+1)^2+4\frac{(m+1)k(k-m)}{m} $$
مربعًا كاملًا وكانت الفردية/الزوجية مناسبة.
وهذا بالضبط ما تختبره الدالة brute_pivots في نقاط التحقق.
نعرّف
$$ A=2n+m+1,\qquad B=2k-m. $$
وعندها
$$ n(n+m+1)=\frac{A^2-(m+1)^2}{4},\qquad k(k-m)=\frac{B^2-m^2}{4}. $$
فتصبح المعادلة
$$ mA^2-(m+1)B^2=m(m+1). $$
نكتب
$$ m(m+1)=s q^2, $$
حيث يكون \(s\) squarefree.
ثم نجري التحويل الخطي
$$ A=(m+1)x+qsy,\qquad B=mx+qsy. $$
وبالتوسيع المباشر نحصل على
$$ mA^2-(m+1)B^2=s q^2(x^2-sy^2). $$
ولأن الطرف الأيسر يجب أن يساوي \(m(m+1)=s q^2\)، فإننا بعد الاختزال نصل إلى معادلة Pell:
$$ x^2-sy^2=1. $$
الصيغ العكسية هي
$$ k=\frac{mx+qsy+m}{2}, $$
$$ n=\frac{(m+1)x+qsy-(m+1)}{2}. $$
كما أن
$$ x=A-B=2(n-k+m)+1. $$
وهذا يفسر مرشحات الكود الثلاثة:
1. يجب أن يكون \(x\) فرديًا،
2. الشرط \(n\ge k\) يكافئ \(x\ge 2m+1\)،
3. يجب أن يكون بسط صيغة \(k\) زوجيًا.
عندما \(m=1\)، يكون \(m(m+1)=2\)، ومن ثم \(s=2\) و\(q=1\)، ومعادلة Pell هي
$$ x^2-2y^2=1. $$
الحل \((3,2)\) يعطي \(k=4\)، والحل التالي \((17,12)\) يعطي \(k=21\).
وعندما \(m=3\)، فإن \(12=3\cdot 2^2\)، لذا \(s=3\) و\(q=2\)، والحل \((7,4)\) يعطي \(k=24\).
وعندما \(m=2\)، فإن \(s=6\) و\(q=1\)، والحل \((49,20)\) يعطي \(k=110\).
من \(n\ge k\) ينتج أن
$$ n(n+m+1)\ge k(k+m+1). $$
وبضم هذا إلى
$$ (m+1)k(k-m)=m\,n(n+m+1) $$
نحصل على
$$ k\ge 2m(m+1). $$
إذن إذا كان \(k\le L\)، فلا بد أن
$$ 2m(m+1)\le L, $$
ومن ثم
$$ m\le \left\lfloor\frac{\sqrt{2L+1}-1}{2}\right\rfloor. $$
وكذلك بما أن
$$ k=\frac{mx+qsy+m}{2}\ge \frac{mx+m}{2}, $$
فإن
$$ x\le \frac{2L-m}{m}, $$
وهو الحد الذي يخزن في x_max.
يمكن لعدة قيم مختلفة من \(m\) أن تشترك في الجزء squarefree نفسه \(s\) في تحليل \(m(m+1)\).
وبما أن معادلة Pell تعتمد فقط على \(s\)، فإن الكود يحلها مرة واحدة لكل مجموعة، ثم يعيد استعمال تيار الحلول نفسه لكل أعضاء تلك المجموعة.
بل إن أزواجًا مختلفة من \((m,n)\) قد تنتج القيمة نفسها لـ \(k\). فمثلًا
$$ 684 $$
تظهر مع \((m,n)=(4,760)\) ومع \((18,684)\)، ولهذا فإزالة التكرار النهائية ضرورية.
تقوم الدالة build_primes ببناء قائمة للأعداد الأولية، بينما تكتب squarefree_and_square_part كل عدد على الصورة \(s q^2\).
لكل قيمة مسموحة من \(m\)، يحسب البرنامج \(m(m+1)\)، ويستخرج \(s\) و\(q\)، ويحدد الحد الآمن x_max، ثم يخزن \((m,q,x_{\max})\) في جدول hash مفهرس بـ \(s\).
تستخدم find_fundamental_pell_limited الكسور المستمرة لإيجاد الحل الأساسي لمعادلة Pell، ثم تولد pell_solutions_up_to بقية الحلول بالعودة القياسية.
بعد ذلك يعيد البرنامج تحويل كل حل إلى مرشح
$$ k=\frac{mx+qsy+m}{2}, $$
ويطبق شروط الفردية والحد الأدنى والزوجية والمدى، ثم يرتب النتائج ويزيل تكرارها ويجمعها.
مجال \(m\) لا يتجاوز \(O(\sqrt{L})\)، ويجري تحليل كل \(m\) مرة واحدة فقط.
أما الكلفة الأساسية فتأتي من توليد حلول Pell لكل فئة squarefree مميزة \(s\)، ثم إسقاط هذه الحلول على المرشحين \(k\) لكل عنصر داخل المجموعة.
ويهيمن على الذاكرة:
1. جدول التجميع حسب \(s\)،
2. قائمة حلول Pell المؤقتة لمجموعة واحدة،
3. متجه قيم pivot المختلفة النهائي.