The \(n\)-th pentagonal number is
$$P_n=\frac{n(3n-1)}{2}.$$
We seek indices \(j<k\) such that both \(P_j+P_k\) and \(P_k-P_j\) are pentagonal, and we want the positive difference
$$D=P_k-P_j$$
to be as small as possible. A naive search over all pairs is infinite, so the real task is to exploit the arithmetic structure of pentagonal numbers and organize the search so that most candidates are rejected quickly.
The implementations are built around three ingredients: the explicit formula for pentagonal numbers, a constant-time test for deciding whether a number is pentagonal, and a monotone scan order that allows safe pruning inside the nested loops.
The first few pentagonal numbers are
$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$
and their growth is quadratic. More importantly for the code, the sequence is strictly increasing because
$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$
This monotonicity is the key invariant used by the search. For a fixed larger index \(k\), if we inspect smaller indices in the order \(j=k-1,k-2,\dots,1\), then \(P_j\) decreases and therefore the difference \(P_k-P_j\) increases step by step.
Suppose \(x=P_n\). Starting from \(x=n(3n-1)/2\), multiply by 24 and complete the square:
$$24x+1=12n(3n-1)+1=(6n-1)^2.$$
So an integer \(x>0\) is pentagonal exactly when \(24x+1\) is a perfect square and
$$n=\frac{1+\sqrt{24x+1}}{6}$$
is an integer. Equivalently, if \(s=\sqrt{24x+1}\), then \(s\) must be integral and \(s\equiv 5 \pmod 6\). The implementations use this inverse test instead of scanning a list for membership. That makes every sum and difference check an \(O(1)\) arithmetic operation.
For \(j<k\), the difference between two pentagonal numbers can be written as
$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}.$$
This formula shows immediately that the gap depends on both the index difference \(k-j\) and the index sum \(k+j\). It is useful conceptually, but the code relies on an even simpler fact: for fixed \(k\), once \(j\) moves downward, the quantity \(P_k-P_j\) can only get larger. Therefore, if a valid pair has already produced a best difference \(D_{\min}\) and the current candidate satisfies
$$P_k-P_j\ge D_{\min},$$
then every later candidate in that same inner loop is automatically worse. The loop can stop immediately without missing a better answer.
The sum condition has no comparable monotone shortcut, so each remaining candidate still needs a direct pentagonal test on
$$P_k+P_j.$$
Take \(P_4=22\) and \(P_7=70\). Their sum is
$$22+70=92,$$
and
$$24\cdot 92+1=2209=47^2,$$
so \(92\) is pentagonal, in fact \(92=P_8\). But their difference is
$$70-22=48,$$
and
$$24\cdot 48+1=1153,$$
which is not a perfect square. So this pair satisfies the sum condition but fails the difference condition. The example shows why both tests are essential: a rare pentagonal sum does not imply a pentagonal difference.
The C++, Python, and Java implementations first precompute the pentagonal numbers \(P_1,P_2,\dots,P_M\) for a configurable upper index bound \(M\); in the provided programs the default is 5000. Keeping these values in an array avoids recomputing the quadratic formula during the pair scan.
To decide whether a sum or difference is pentagonal, the implementation applies the inverse criterion \(24x+1=(6n-1)^2\). One version uses an integer square root to check the discriminant exactly; the other two compute a square root, round to the nearest candidate index, and then substitute that index back into \(n(3n-1)/2\). In all three cases, the final acceptance step is exact because the recovered index must reproduce the original value. Before the full search begins, the programs also verify this predicate on small known cases such as 12 and 35, reject 36, and confirm the larger pentagonal number 40755.
The main search enumerates the larger index increasingly. For each larger index, it walks the smaller index downward, computes the current difference and sum, and uses the monotonicity of the difference to stop the inner loop as soon as the current gap is no longer better than the best valid one already found. Only the candidates that survive this pruning are tested for the two pentagonal conditions. Whenever both tests succeed, the best difference is updated. After all indices up to the chosen bound have been processed, that smallest recorded difference is returned.
If \(M\) is the search bound on the larger index, precomputing the pentagonal table costs \(O(M)\) time and \(O(M)\) space. The nested scan over pairs costs \(O(M^2)\) time in the worst case, because it may inspect on the order of \(M(M-1)/2\) pairs. Each inspection performs only constant-time arithmetic together with two constant-time pentagonality checks.
The pruning rule often saves a noticeable fraction of the inner loop once a good candidate has been found, but it does not change the worst-case asymptotic bound. So the method is still a quadratic search in theory, yet it is practical here because the bound is modest and the direct pentagonal test is very cheap.
Die \(n\)-te pentagonale Zahl ist
$$P_n=\frac{n(3n-1)}{2}.$$
Gesucht sind Indizes \(j<k\), so dass sowohl \(P_j+P_k\) als auch \(P_k-P_j\) wieder pentagonal sind. Dabei soll die positive Differenz
$$D=P_k-P_j$$
minimal sein. Eine naive Suche über alle Paare ist unendlich; entscheidend ist also, die arithmetische Struktur pentagonaler Zahlen so auszunutzen, dass die Kandidaten systematisch und mit früher Verwerfung geprüft werden.
Die Implementierungen beruhen auf drei Bausteinen: der expliziten Formel für pentagonale Zahlen, einem direkten Test auf Pentagonalität und einer Suchreihenfolge, in der die Differenz monoton wächst und deshalb abgeschnitten werden kann.
Die ersten Werte lauten
$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$
und wachsen quadratisch. Für den Code ist vor allem wichtig, dass die Folge streng steigt, denn
$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$
Genau diese Monotonie ist die zentrale Invariante der Suche. Wenn man für festes größeres \(k\) die kleineren Indizes in der Reihenfolge \(j=k-1,k-2,\dots,1\) durchläuft, dann wird \(P_j\) kleiner und damit \(P_k-P_j\) Schritt für Schritt größer.
Sei \(x=P_n\). Aus \(x=n(3n-1)/2\) folgt nach Multiplikation mit 24 und quadratischer Ergänzung
$$24x+1=12n(3n-1)+1=(6n-1)^2.$$
Damit ist eine ganze Zahl \(x>0\) genau dann pentagonal, wenn \(24x+1\) ein perfektes Quadrat ist und
$$n=\frac{1+\sqrt{24x+1}}{6}$$
ganzzahlig ist. Äquivalent dazu muss für \(s=\sqrt{24x+1}\) gelten: \(s\) ist ganz und \(s\equiv 5 \pmod 6\). Die Implementierungen verwenden diesen inversen Test anstelle einer linearen Mitgliedschaftssuche. Dadurch werden Summen und Differenzen mit konstantem Aufwand geprüft.
Für \(j<k\) lässt sich die Differenz als
$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}$$
schreiben. Diese Identität zeigt, dass die Differenz sowohl vom Indexabstand \(k-j\) als auch von der Summe \(k+j\) abhängt. Für die Implementierung ist aber noch wichtiger: Bei festem \(k\) kann \(P_k-P_j\) nur wachsen, wenn \(j\) kleiner wird. Hat man also bereits eine gültige beste Differenz \(D_{\min}\) gefunden und gilt aktuell
$$P_k-P_j\ge D_{\min},$$
dann kann kein späterer Kandidat derselben inneren Schleife mehr besser sein. Der Rest dieser Schleife darf sofort abgebrochen werden.
Für die Summenbedingung gibt es keine entsprechende monotone Abkürzung. Deshalb muss für jeden verbleibenden Kandidaten weiterhin direkt getestet werden, ob
$$P_k+P_j$$
pentagonal ist.
Betrachte \(P_4=22\) und \(P_7=70\). Ihre Summe ist
$$22+70=92,$$
und es gilt
$$24\cdot 92+1=2209=47^2.$$
Also ist 92 pentagonal, sogar \(92=P_8\). Die Differenz ist jedoch
$$70-22=48,$$
und
$$24\cdot 48+1=1153$$
ist kein perfektes Quadrat. Das Paar erfüllt also die Summenbedingung, aber nicht die Differenzbedingung. Gerade deshalb müssen beide Prüfungen unabhängig voneinander durchgeführt werden.
Die C++-, Python- und Java-Implementierungen berechnen zunächst die Werte \(P_1,P_2,\dots,P_M\) bis zu einer konfigurierbaren oberen Indexgrenze \(M\); in den bereitgestellten Programmen ist der Standardwert 5000. Diese Vorberechnung vermeidet, dass die quadratische Formel in der Doppelschleife ständig neu ausgewertet werden muss.
Der Pentagonalitätstest basiert direkt auf dem Kriterium \(24x+1=(6n-1)^2\). Eine Version nutzt eine exakte ganzzahlige Quadratwurzelprüfung des Diskriminanten, die beiden anderen berechnen eine Quadratwurzel, runden auf den nächstliegenden Kandidatenindex und setzen diesen dann wieder in \(n(3n-1)/2\) ein. In allen drei Fällen ist die letzte Entscheidung exakt, weil der rekonstruierte Index den ursprünglichen Wert reproduzieren muss. Vor der eigentlichen Suche prüfen die Programme den Test zusätzlich an bekannten kleinen Werten wie 12 und 35, verwerfen 36 und kontrollieren außerdem die größere pentagonale Zahl 40755.
Danach beginnt die eigentliche Paarsuche: Der größere Index wird aufsteigend durchlaufen, der kleinere Index für jedes feste Paar nach unten gezählt. Aus Summe und Differenz wird zunächst die Differenz gegen das bisher beste Ergebnis verglichen. Sobald sie nicht mehr kleiner sein kann, wird die innere Schleife abgebrochen. Nur die verbliebenen Kandidaten werden mit dem direkten Pentagonalitätstest für Summe und Differenz geprüft. Wenn beide Bedingungen erfüllt sind, wird die beste Differenz aktualisiert. Nach Abschluss aller Indizes bis zur gewählten Grenze liefert die Implementierung die kleinste gefundene Differenz zurück.
Ist \(M\) die obere Suchgrenze für den größeren Index, dann kostet die Vorberechnung der pentagonalen Zahlen \(O(M)\) Zeit und \(O(M)\) Speicher. Die verschachtelte Paarsuche benötigt im schlechtesten Fall \(O(M^2)\) Zeit, weil ungefähr \(M(M-1)/2\) Paare untersucht werden können. Jede einzelne Prüfung besteht nur aus konstant vielen arithmetischen Operationen und zwei Pentagonalitätstests in konstanter Zeit.
Die Abbruchregel spart in der Praxis oft einen merklichen Teil der inneren Schleifen, sobald ein guter Kandidat gefunden wurde. An der asymptotischen Worst-Case-Schranke ändert das jedoch nichts. Theoretisch bleibt das Verfahren also quadratisch, praktisch ist es für die hier verwendete moderate Grenze dennoch gut geeignet.
\(n\). beşgen sayı
$$P_n=\frac{n(3n-1)}{2}$$
formülüyle tanımlanır. Aradığımız şey, \(j<k\) olacak şekilde hem \(P_j+P_k\) hem de \(P_k-P_j\) yine beşgen sayı olan bir indeks çifti bulmaktır. Ayrıca pozitif farkın
$$D=P_k-P_j$$
olabildiğince küçük olması gerekir. Tüm çiftleri doğrudan taramak sonsuz bir arama alanı verir; bu yüzden çözüm, beşgen sayıların cebirsel yapısını kullanıp adayları çok erken elemek üzerine kuruludur.
Uygulamalar üç temel fikri bir araya getirir: beşgen sayıların açık formülü, bir sayının beşgen olup olmadığını sabit zamanda test eden ters kriter ve iç döngüde güvenli kırılma sağlayan tekdüze tarama düzeni.
İlk birkaç terim
$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$
şeklindedir ve dizi kuadratik büyür. Kod açısından asıl önemli nokta, dizinin sıkı artan olmasıdır; çünkü
$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$
Arama mantığının dayandığı temel değişmez tam olarak budur. Daha büyük indeks \(k\) sabit tutulup küçük indeksler \(j=k-1,k-2,\dots,1\) sırasıyla denenirse, \(P_j\) küçülür; dolayısıyla \(P_k-P_j\) adım adım büyür.
\(x=P_n\) olsun. \(x=n(3n-1)/2\) eşitliğini 24 ile çarpıp kare tamamlayınca
$$24x+1=12n(3n-1)+1=(6n-1)^2$$
elde edilir. Bu yüzden \(x>0\) tam sayısı ancak ve ancak \(24x+1\) tam kare ise ve
$$n=\frac{1+\sqrt{24x+1}}{6}$$
bir tam sayı çıkıyorsa beşgendir. Aynı şey şu biçimde de söylenebilir: \(s=\sqrt{24x+1}\) için \(s\) tam sayı olmalı ve \(s\equiv 5 \pmod 6\) koşulu sağlanmalıdır. Uygulamalar, üyeliği bir tabloda aramak yerine bu ters testi kullanır. Böylece her toplam ve fark kontrolü sabit maliyetli bir aritmetik işlemi olur.
\(j<k\) için iki beşgen sayının farkı
$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}$$
biçiminde yazılır. Bu kimlik, farkın hem indeks farkına \(k-j\) hem de indeks toplamına \(k+j\) bağlı olduğunu gösterir. Fakat kodun kullandığı daha pratik bilgi şudur: \(k\) sabitken \(j\) küçüldükçe \(P_k-P_j\) yalnızca büyür. O halde daha önce geçerli bir çift bulunmuş ve onun en iyi farkı \(D_{\min}\) ise, güncel aday için
$$P_k-P_j\ge D_{\min}$$
olduğu anda aynı iç döngüde bundan sonraki hiçbir aday daha iyi olamaz. Döngüyü o noktada kırmak matematiksel olarak tamamen güvenlidir.
Toplam koşulu için benzer bir tekdüzelik kısayolu yoktur. Bu nedenle ayakta kalan her adayda
$$P_k+P_j$$
ifadesinin de doğrudan beşgen testiyle kontrol edilmesi gerekir.
\(P_4=22\) ve \(P_7=70\) alınsın. Toplamları
$$22+70=92$$
olur ve
$$24\cdot 92+1=2209=47^2$$
olduğundan 92 beşgendir; hatta \(92=P_8\). Ama farkları
$$70-22=48$$
olur ve
$$24\cdot 48+1=1153$$
tam kare değildir. Yani bu çift toplam koşulunu sağlasa da fark koşulunda elenir. Örnek, neden iki testin de bağımsız olarak yapılması gerektiğini açıkça gösterir.
C++, Python ve Java uygulamaları önce \(P_1,P_2,\dots,P_M\) değerlerini önceden hesaplar; burada \(M\) yapılandırılabilir üst indeks sınırıdır ve verilen sürümlerde varsayılan değer 5000'dir. Bu tablo, ikili tarama sırasında aynı beşgen sayıları tekrar tekrar üretme maliyetini ortadan kaldırır.
Bir toplamın ya da farkın beşgen olup olmadığı, \(24x+1=(6n-1)^2\) ölçütüyle sınanır. Sürümlerden biri diskriminantı tam sayı kareköküyle kesin olarak kontrol eder; diğer ikisi karekök alıp en yakın aday indeksi yuvarlar ve sonra bu adayı yeniden \(n(3n-1)/2\) formülüne yerleştirerek doğrular. Üçünde de son kabul adımı kesindir; çünkü aday indeksin orijinal sayıyı aynen üretmesi gerekir. Tam aramadan önce 12 ve 35 gibi bilinen beşgen değerler doğrulanır, 36'nın beşgen olmadığı kontrol edilir ve 40755 üzerinde daha büyük bir sağlamlık testi yapılır.
Ana arama kısmında büyük indeks artan sırada dolaşılır. Her büyük indeks için küçük indeks geriye doğru azaltılır, o anki fark ve toplam hesaplanır ve fark artık eldeki en iyi sonuçtan küçük olamayacak hale gelmişse iç döngü hemen sonlandırılır. Bu budamadan kurtulan adaylar için hem fark hem toplam beşgen testinden geçirilir. Her iki koşul da sağlanıyorsa en iyi fark güncellenir. Seçilen üst sınıra kadar tüm indeksler işlendiğinde, kaydedilmiş en küçük fark döndürülür.
Büyük indeks için kullanılan üst sınır \(M\) ise, beşgen tabloyu oluşturmak \(O(M)\) zaman ve \(O(M)\) bellek gerektirir. Çiftler üzerindeki iç içe tarama en kötü durumda \(O(M^2)\) zamandır; çünkü yaklaşık \(M(M-1)/2\) aday incelenebilir. Her adayda yalnızca sabit sayıda aritmetik işlem ve sabit zamanda çalışan iki beşgenlik testi yapılır.
Erken kırılma kuralı, iyi bir aday bulunduktan sonra iç döngünün hatırı sayılır bir bölümünü pratikte kesebilir; ancak bu, en kötü durum asimptotiğini değiştirmez. Yani yöntem teoride hâlâ kuadratiktir, fakat burada kullanılan mütevazı sınır ve ucuz sayı testi sayesinde uygulamada yeterince hızlıdır.
El \(n\)-ésimo número pentagonal es
$$P_n=\frac{n(3n-1)}{2}.$$
Buscamos índices \(j<k\) tales que tanto \(P_j+P_k\) como \(P_k-P_j\) vuelvan a ser pentagonales. Además, la diferencia positiva
$$D=P_k-P_j$$
debe ser lo más pequeña posible. Un recorrido ingenuo por todos los pares sería infinito; por eso la solución real depende de explotar la estructura aritmética de los números pentagonales y descartar candidatos muy pronto.
Las implementaciones combinan tres ideas: la fórmula cerrada de los números pentagonales, un criterio directo para decidir si un entero es pentagonal y un orden de exploración donde la diferencia crece de manera monótona dentro del bucle interno.
Los primeros términos son
$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$
y su crecimiento es cuadrático. Para el algoritmo, lo crucial es que la sucesión sea estrictamente creciente, ya que
$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$
Esa monotonía es la invariante central del barrido. Si fijamos el índice mayor \(k\) y probamos los índices menores en el orden \(j=k-1,k-2,\dots,1\), entonces \(P_j\) va disminuyendo y, por lo tanto, la diferencia \(P_k-P_j\) va aumentando paso a paso.
Supongamos que \(x=P_n\). A partir de \(x=n(3n-1)/2\), al multiplicar por 24 y completar el cuadrado obtenemos
$$24x+1=12n(3n-1)+1=(6n-1)^2.$$
Así, un entero \(x>0\) es pentagonal exactamente cuando \(24x+1\) es un cuadrado perfecto y
$$n=\frac{1+\sqrt{24x+1}}{6}$$
resulta entero. De forma equivalente, si \(s=\sqrt{24x+1}\), entonces \(s\) debe ser entero y cumplir \(s\equiv 5 \pmod 6\). Las implementaciones usan este criterio inverso en lugar de buscar pertenencia en una lista. Eso convierte cada comprobación de suma o diferencia en una operación aritmética de costo constante.
Para \(j<k\), la diferencia entre dos números pentagonales puede expresarse como
$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}.$$
La identidad deja claro que la brecha depende tanto de \(k-j\) como de \(k+j\). Sin embargo, el código explota una observación todavía más simple: con \(k\) fijo, al decrecer \(j\), la cantidad \(P_k-P_j\) solo puede aumentar. Por lo tanto, si ya existe una mejor diferencia válida \(D_{\min}\) y el candidato actual satisface
$$P_k-P_j\ge D_{\min},$$
ningún candidato posterior dentro de ese mismo bucle interno podrá mejorar el resultado. El resto del bucle puede cortarse de inmediato.
La condición sobre la suma no tiene un atajo monótono comparable. Por eso, para cada candidato que sobrevive al corte todavía hay que comprobar directamente si
$$P_k+P_j$$
es pentagonal.
Tomemos \(P_4=22\) y \(P_7=70\). Su suma es
$$22+70=92,$$
y se cumple que
$$24\cdot 92+1=2209=47^2.$$
Luego 92 sí es pentagonal; de hecho, \(92=P_8\). Pero la diferencia vale
$$70-22=48,$$
y
$$24\cdot 48+1=1153$$
no es un cuadrado perfecto. Así que este par supera la prueba de la suma pero falla la de la diferencia. El ejemplo muestra por qué ambas condiciones son realmente independientes.
Las implementaciones en C++, Python y Java primero precalculan los valores \(P_1,P_2,\dots,P_M\) hasta una cota superior de índice configurable \(M\); en los programas suministrados, el valor por defecto es 5000. Guardar esta tabla evita volver a evaluar la fórmula cuadrática cada vez que se examina un par.
Para decidir si una suma o una diferencia es pentagonal, la implementación usa el criterio inverso \(24x+1=(6n-1)^2\). Una versión aplica una raíz cuadrada entera para verificar el discriminante de forma exacta; las otras dos calculan una raíz cuadrada ordinaria, redondean al índice candidato más cercano y luego sustituyen ese índice de nuevo en \(n(3n-1)/2\). En los tres casos la aceptación final es exacta, porque el índice reconstruido debe regenerar el valor original. Antes del barrido completo, los programas además validan la prueba con casos pequeños conocidos como 12 y 35, rechazan 36 y comprueban también el valor pentagonal mayor 40755.
La búsqueda principal recorre el índice mayor en orden creciente. Para cada índice mayor, el índice menor desciende, se calculan la diferencia y la suma, y la monotonía de la diferencia se usa para cortar el bucle interno tan pronto como la brecha actual ya no pueda mejorar la mejor válida conocida. Solo los candidatos que sobreviven a ese filtro pasan por las dos pruebas de pentagonalidad. Siempre que ambas pruebas resultan positivas, la mejor diferencia se actualiza. Tras procesar todos los índices hasta la cota elegida, se devuelve la diferencia mínima registrada.
Si \(M\) es la cota de búsqueda para el índice mayor, la precalculación de la tabla pentagonal cuesta \(O(M)\) tiempo y \(O(M)\) espacio. El barrido anidado sobre pares cuesta \(O(M^2)\) tiempo en el peor caso, porque puede examinar alrededor de \(M(M-1)/2\) pares. Cada examen realiza solo aritmética de tiempo constante y dos comprobaciones de pentagonalidad también de tiempo constante.
La regla de corte suele ahorrar una fracción apreciable del bucle interno una vez que ya se ha encontrado un buen candidato, pero no modifica la cota asintótica de peor caso. Por eso el método sigue siendo cuadrático en teoría, aunque sea perfectamente práctico aquí gracias a la cota moderada y a la prueba aritmética tan barata.
第 \(n\) 个五边形数定义为
$$P_n=\frac{n(3n-1)}{2}$$
题目要求寻找 \(j<k\) 使得 \(P_j+P_k\) 与 \(P_k-P_j\) 同时仍是五边形数，并且希望正差值
$$D=P_k-P_j$$
尽可能小。直接把所有下标对都枚举一遍会得到一个无穷搜索空间，因此真正的关键不是“暴力试到成功”，而是利用五边形数的代数结构，把绝大多数候选在很早的阶段就排除掉。
这三份实现的核心完全一致：先利用五边形数的显式公式生成候选，再用一个常数时间的“是否为五边形数”判定式检查和与差，最后按照一种带有单调性的顺序扫描下标对，从而在内层循环中安全剪枝。
前几项五边形数是
$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$
它们按二次速度增长。对程序来说，更重要的是这个序列严格递增，因为
$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0$$
这正是搜索过程中最重要的不变量。固定较大的下标 \(k\) 以后，如果较小的下标按 \(j=k-1,k-2,\dots,1\) 的顺序向下扫描，那么 \(P_j\) 会不断变小，因此差值 \(P_k-P_j\) 会一步一步变大。后面所有剪枝都建立在这个单调性之上。
设某个整数 \(x\) 满足 \(x=P_n\)。从
$$x=\frac{n(3n-1)}{2}$$
出发，乘以 24 并配方，可得
$$24x+1=12n(3n-1)+1=(6n-1)^2$$
因此，正整数 \(x\) 是五边形数，当且仅当 \(24x+1\) 是完全平方数，并且
$$n=\frac{1+\sqrt{24x+1}}{6}$$
是整数。等价地说，若记 \(s=\sqrt{24x+1}\)，那么 \(s\) 必须是整数且满足 \(s\equiv 5 \pmod 6\)。这就是实现中使用的逆向判定法。它避免了对列表做成员搜索，使得每一次“和是否为五边形数”“差是否为五边形数”的判断都只需要常数时间的算术操作。
对于 \(j<k\)，两个五边形数之差可以写成
$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}$$
这个公式表明，差值同时依赖于下标差 \(k-j\) 和下标和 \(k+j\)。不过，代码真正利用的是一个更直接的结论：当 \(k\) 固定而 \(j\) 向下减小时，\(P_k-P_j\) 只会变大，不会变小。于是，一旦已经找到某个合法下标对，其当前最优差值记为 \(D_{\min}\)，而当前候选已经满足
$$P_k-P_j\ge D_{\min},$$
那么同一个内层循环中后续所有更小的 \(j\) 都不可能得到更优解，可以立即停止这一轮扫描。
和式条件没有类似的单调捷径，所以所有通过差值剪枝的候选仍然必须继续检查
$$P_k+P_j$$
是否也是五边形数。
来看 \(P_4=22\) 与 \(P_7=70\)。它们的和是
$$22+70=92$$
并且
$$24\cdot 92+1=2209=47^2$$
所以 92 的确是五边形数，事实上 \(92=P_8\)。但是它们的差是
$$70-22=48$$
而
$$24\cdot 48+1=1153$$
不是完全平方数，因此 48 不是五边形数。这个例子非常典型：它说明“和满足条件”并不足够，差值条件必须单独检查，两者缺一不可。
C++、Python 和 Java 实现都会先预计算 \(P_1,P_2,\dots,P_M\)，其中 \(M\) 是可配置的最大下标，给定程序的默认值是 5000。把这些值保存下来以后，主搜索阶段就不需要反复重新计算五边形公式。
判定某个和或差是否为五边形数时，实现采用的都是上面的逆向条件 \(24x+1=(6n-1)^2\)。其中一个版本先用整数平方根精确检查判别式是否为完全平方数；另外两个版本先求平方根，再把对应的下标候选四舍五入，最后重新代回 \(n(3n-1)/2\) 验证是否恰好还原原值。虽然具体写法略有差异，但三者最后都依赖“代回原公式必须精确重构”这一点，因此判定结果是一致且准确的。正式搜索开始前，程序还会用一些已知样例做健全性检查，例如确认 12 和 35 是五边形数、确认 36 不是五边形数，并额外检查较大的已知五边形数 40755。
真正的搜索过程按较大下标递增进行。对每个固定的较大下标，较小下标从邻近位置开始向下扫描。程序先计算当前差值和当前和，然后利用“差值只会越来越大”的单调性判断是否应该提前退出内层循环；如果当前差值已经不可能优于已知最优值，这一轮后面的候选就没有继续检查的必要。只有通过这一步筛选的候选，才会再去检查差值与和是否同时为五边形数。一旦两个条件都成立，就更新当前最优差值。所有下标都处理完之后，程序返回整个搜索过程中记录到的最小差值。
如果把较大下标的搜索上界记为 \(M\)，那么预计算五边形数表需要 \(O(M)\) 时间和 \(O(M)\) 空间。随后对下标对的双重扫描在最坏情况下需要 \(O(M^2)\) 时间，因为理论上可能检查大约 \(M(M-1)/2\) 个候选对。每个候选只做常数次算术运算，以及两个常数时间的五边形数判定。
内层循环的提前终止在实践中往往能节省掉相当一部分比较，尤其是在已经找到较好的候选之后，但它并不会改变最坏情况下的渐近上界。因此，这个方法从理论上看仍然是二次时间搜索；不过在这里，二次搜索配合廉价的判定公式和适中的上界，已经足够高效。
\(n\)-е пятиугольное число задается формулой
$$P_n=\frac{n(3n-1)}{2}.$$
Нужно найти индексы \(j<k\), для которых и сумма \(P_j+P_k\), и разность \(P_k-P_j\) снова являются пятиугольными числами. При этом положительная разность
$$D=P_k-P_j$$
должна быть минимальной. Полный перебор всех пар без использования структуры задачи бесполезен, потому что пространство поиска бесконечно. Поэтому решение строится на точном арифметическом критерии и на порядке обхода, позволяющем рано отсекать заведомо плохие пары.
Все три реализации опираются на одни и те же идеи: явную формулу пятиугольных чисел, быстрый обратный тест на пятиугольность и такой порядок просмотра пар индексов, при котором разность внутри внутреннего цикла меняется монотонно.
Первые члены последовательности таковы:
$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$
Рост квадратичный, но для алгоритма важнее другое: последовательность строго возрастает, поскольку
$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$
Именно эта монотонность дает главный инвариант поиска. Если фиксировать больший индекс \(k\) и перебирать меньший индекс в порядке \(j=k-1,k-2,\dots,1\), то \(P_j\) уменьшается, а значит, разность \(P_k-P_j\) растет шаг за шагом.
Пусть \(x=P_n\). Из равенства \(x=n(3n-1)/2\), после умножения на 24 и выделения квадрата, получаем
$$24x+1=12n(3n-1)+1=(6n-1)^2.$$
Следовательно, положительное целое \(x\) является пятиугольным тогда и только тогда, когда \(24x+1\) есть точный квадрат и
$$n=\frac{1+\sqrt{24x+1}}{6}$$
оказывается целым. Эквивалентная формулировка: если \(s=\sqrt{24x+1}\), то \(s\) должен быть целым и удовлетворять сравнению \(s\equiv 5 \pmod 6\). Реализации используют именно этот обратный критерий, а не поиск числа в заранее построенном множестве. Поэтому проверка суммы и разности занимает постоянное время.
Для \(j<k\) разность двух пятиугольных чисел равна
$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}.$$
Эта формула показывает, что величина разности зависит и от разрыва индексов \(k-j\), и от их суммы \(k+j\). Но для кода важнее более простое следствие: при фиксированном \(k\) и убывающем \(j\) величина \(P_k-P_j\) может только увеличиваться. Поэтому, если уже найдено некоторое лучшее допустимое значение \(D_{\min}\), и очередной кандидат удовлетворяет неравенству
$$P_k-P_j\ge D_{\min},$$
то все последующие кандидаты в том же внутреннем цикле будут не лучше. Значит, внутренний цикл можно немедленно оборвать без риска пропустить оптимальный ответ.
Для суммы такого монотонного сокращения нет, поэтому каждую уцелевшую пару все равно нужно отдельно проверять на условие
$$P_k+P_j$$
быть пятиугольным числом.
Возьмем \(P_4=22\) и \(P_7=70\). Их сумма равна
$$22+70=92,$$
и
$$24\cdot 92+1=2209=47^2.$$
Значит, 92 действительно пятиугольно, более того \(92=P_8\). Но разность равна
$$70-22=48,$$
а
$$24\cdot 48+1=1153$$
не является точным квадратом. Следовательно, пара проходит проверку на сумму, но не проходит проверку на разность. Это хорошо показывает, почему нужно проверять оба условия по отдельности.
Реализации на C++, Python и Java сначала заранее вычисляют значения \(P_1,P_2,\dots,P_M\), где \(M\) — настраиваемая верхняя граница индекса; в предоставленных программах по умолчанию используется 5000. Такой массив нужен затем, чтобы не пересчитывать формулу пятиугольного числа при каждом просмотре пары.
Проверка пятиугольности основана на критерии \(24x+1=(6n-1)^2\). В одной версии дискриминант проверяется через точный целочисленный квадратный корень; в двух других сначала берется обычный квадратный корень, затем восстанавливается ближайший кандидат на индекс, и после этого значение пересчитывается назад по формуле \(n(3n-1)/2\). Во всех трех случаях окончательное решение точное, потому что восстановленный индекс обязан снова дать исходное число. До полного перебора программы дополнительно проверяют этот тест на известных примерах: подтверждают пятиугольность 12 и 35, отклоняют 36 и проверяют более крупное пятиугольное число 40755.
Основной поиск устроен так: больший индекс перебирается по возрастанию, а меньший для каждого фиксированного большего индекса идет вниз. На каждом шаге вычисляются текущие сумма и разность. Затем используется монотонность разности: как только текущий разрыв уже не лучше найденного лучшего, внутренний цикл завершается. Только кандидаты, прошедшие эту отсечку, тестируются на обе пятиугольные условия. Если оба условия выполнены, лучшее значение разности обновляется. После обработки всех индексов до выбранной границы возвращается минимальная найденная разность.
Если \(M\) — верхняя граница для большего индекса, то предварительное вычисление таблицы пятиугольных чисел требует \(O(M)\) времени и \(O(M)\) памяти. Двойной перебор пар в худшем случае занимает \(O(M^2)\) времени, так как потенциально рассматривается около \(M(M-1)/2\) пар. Каждая проверка использует только постоянное число арифметических операций и два теста на пятиугольность постоянной стоимости.
Правило раннего выхода часто заметно сокращает внутренний цикл на практике, когда уже найден неплохой кандидат, но оно не меняет асимптотику худшего случая. Поэтому теоретически метод остается квадратичным, однако для умеренной границы и дешевого арифметического теста этого более чем достаточно.
يُعرَّف العدد الخماسي رقم \(n\) بالعلاقة
$$P_n=\frac{n(3n-1)}{2}.$$
المطلوب هو إيجاد فهرسين \(j<k\) بحيث يكون كلٌّ من \(P_j+P_k\) و\(P_k-P_j\) عددًا خماسيًا أيضًا، مع جعل الفرق الموجب
$$D=P_k-P_j$$
أصغر ما يمكن. التعداد المباشر لجميع الأزواج لا يفيد، لأن فضاء البحث غير منتهٍ. لذلك تعتمد الفكرة الصحيحة على البنية الحسابية للأعداد الخماسية وعلى ترتيب بحث يسمح باستبعاد عدد كبير من الأزواج قبل إجراء فحوصات مكلفة غير ضرورية.
تعتمد الحلول الثلاثة على ثلاثة عناصر مترابطة: صيغة صريحة للأعداد الخماسية، واختبار مباشر يحدد ما إذا كان عدد صحيح معين خماسيًا، وترتيب مسح يجعل الفرق يزداد رتيبًا داخل الحلقة الداخلية، مما يسمح بقطعها مبكرًا بأمان.
بدايات المتتالية هي
$$1,\ 5,\ 12,\ 22,\ 35,\ 51,\ 70,\ 92,\dots$$
ونموها تربيعي. لكن الأهم برمجيًا هو أنها متزايدة تمامًا، لأن
$$P_{n+1}-P_n=\frac{(n+1)(3n+2)-n(3n-1)}{2}=3n+1>0.$$
وهذه الرتابة هي الثابت الأساسي الذي تعتمد عليه الخوارزمية. فإذا ثبتنا الفهرس الأكبر \(k\) وجعلنا الفهرس الأصغر يسير تنازليًا وفق \(j=k-1,k-2,\dots,1\)، فإن \(P_j\) يتناقص باستمرار، وبالتالي يزداد الفرق \(P_k-P_j\) خطوة بعد خطوة.
افترض أن \(x=P_n\). انطلاقًا من
$$x=\frac{n(3n-1)}{2}$$
ثم بالضرب في 24 وإكمال المربع نحصل على
$$24x+1=12n(3n-1)+1=(6n-1)^2.$$
إذن يكون العدد الصحيح الموجب \(x\) خماسيًا إذا وفقط إذا كان \(24x+1\) مربعًا كاملاً، وكان
$$n=\frac{1+\sqrt{24x+1}}{6}$$
عددًا صحيحًا. وبصيغة مكافئة، إذا كتبنا \(s=\sqrt{24x+1}\) فلا بد أن يكون \(s\) عددًا صحيحًا وأن يحقق \(s\equiv 5 \pmod 6\). هذا هو الاختبار العكسي الذي تستخدمه الشيفرة بدلًا من البحث عن العضوية في قائمة أو مجموعة. وبذلك تصبح كل عملية تحقق من المجموع أو الفرق عملية حسابية ذات كلفة ثابتة.
عندما يكون \(j<k\)، يمكن كتابة الفرق بين عددين خماسيين على الصورة
$$P_k-P_j=\frac{k(3k-1)-j(3j-1)}{2}=\frac{(k-j)\bigl(3(k+j)-1\bigr)}{2}.$$
توضح هذه الصيغة أن الفرق يعتمد معًا على فجوة الفهارس \(k-j\) وعلى مجموعها \(k+j\). لكن الفائدة العملية الأهم في الشيفرة هي الملاحظة الأبسط: عند تثبيت \(k\)، فإن إنقاص \(j\) لا يمكن إلا أن يزيد القيمة \(P_k-P_j\). لذلك، إذا كانت لدينا بالفعل أفضل قيمة صحيحة معروفة \(D_{\min}\)، ووصلنا أثناء المسح إلى مرشح يحقق
$$P_k-P_j\ge D_{\min},$$
فإن كل ما سيأتي بعده في الحلقة الداخلية سيكون أسوأ بالضرورة، ومن ثم يمكن إيقاف تلك الحلقة فورًا من دون أي خطر على صحة الجواب النهائي.
أما شرط المجموع فلا يملك اختصارًا رتيبًا مماثلًا، ولهذا يجب بعد اجتياز خطوة القطع أن نتحقق مباشرة أيضًا من أن
$$P_k+P_j$$
عدد خماسي.
خذ \(P_4=22\) و\(P_7=70\). المجموع هو
$$22+70=92$$
ولدينا
$$24\cdot 92+1=2209=47^2$$
إذًا 92 عدد خماسي بالفعل، بل إن \(92=P_8\). لكن الفرق يساوي
$$70-22=48$$
وفي المقابل
$$24\cdot 48+1=1153$$
ليس مربعًا كاملاً. هذا يعني أن الزوج يحقق شرط المجموع لكنه يفشل في شرط الفرق. والمثال يوضح بدقة لماذا لا يكفي أن يكون أحد الشرطين صحيحًا؛ فلا بد من تحقق الشرطين معًا.
تبدأ تطبيقات C++ وPython وJava بحساب القيم \(P_1,P_2,\dots,P_M\) مسبقًا حتى حد أعلى قابل للضبط هو \(M\)، والقيمة الافتراضية في البرامج المقدمة هي 5000. الاحتفاظ بهذه القيم في مصفوفة يمنع إعادة حساب صيغة العدد الخماسي في كل مرة تتم فيها دراسة زوج جديد.
لاختبار ما إذا كان مجموع أو فرق ما خماسيًا، تستخدم الشيفرة المعيار العكسي \(24x+1=(6n-1)^2\). إحدى النسخ تعتمد على جذر تربيعي صحيح للتحقق بدقة من كون المميز مربعًا كاملاً؛ والنسختان الأخريان تحسبان جذرًا تربيعيًا عاديًا، ثم تقربان فهرس المرشح الأقرب، وبعد ذلك تعيدان هذا الفهرس إلى الصيغة \(n(3n-1)/2\) للتأكد من استعادة العدد الأصلي تمامًا. وعلى الرغم من اختلاف التفاصيل التنفيذية، فإن القرار النهائي في الحالات الثلاث دقيق لأنه لا يتم قبول أي مرشح إلا إذا أعاد توليد القيمة نفسها. وقبل بدء البحث الكامل، تُجرى أيضًا اختبارات تحقق صغيرة: تأكيد أن 12 و35 عددان خماسيان، والتأكد من أن 36 ليس خماسيًا، وفحص العدد الخماسي الأكبر 40755.
بعد ذلك تبدأ عملية البحث الرئيسية. يسير الفهرس الأكبر تصاعديًا، ولكل قيمة منه يتحرك الفهرس الأصغر تنازليًا. في كل خطوة تُحسب قيمة الفرق وقيمة المجموع. ثم تستغل الشيفرة رتابة الفرق: فإذا أصبحت الفجوة الحالية غير قادرة على تحسين أفضل فجوة صحيحة عُثر عليها سابقًا، تتوقف الحلقة الداخلية مباشرة. أما الأزواج التي تنجو من هذا القطع فتخضع لاختبار الخماسية لكل من الفرق والمجموع. وعند نجاح الاختبارين معًا، تُحدَّث أفضل قيمة للفرق. وبعد إتمام جميع الفهارس حتى الحد المختار، تُعاد أصغر فجوة تم العثور عليها أثناء المسح.
إذا رمزنا إلى حد البحث الأعلى للفهرس الأكبر بالرمز \(M\)، فإن بناء جدول الأعداد الخماسية يحتاج إلى \(O(M)\) زمنًا و\(O(M)\) ذاكرة. أما المسح المتداخل للأزواج فيأخذ \(O(M^2)\) زمنًا في أسوأ الحالات، لأنه قد يفحص ما يقارب \(M(M-1)/2\) زوجًا. وكل فحص يتكون فقط من عدد ثابت من العمليات الحسابية ومن اختبارين للخماسية بزمن ثابت.
قاعدة الإنهاء المبكر توفر عادة جزءًا ملحوظًا من عمل الحلقة الداخلية بعد العثور على مرشح جيد، لكنها لا تغير رتبة التعقيد الأسوأ. لذلك تظل الطريقة تربيعية من الناحية النظرية، لكنها عملية جدًا هنا لأن الحد المستخدم متوسط واختبار الخماسية رخيص حسابيًا.