We seek palindromic integers \(n\) that admit exactly four distinct representations of the form
$$n=a^2+b^3,\qquad a,b \gt 1.$$
The solver must identify the five smallest such palindromes and sum them, but the final Project Euler value is intentionally omitted here.
For a fixed integer \(n\), define the representation count
$$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}.$$
We accept a candidate exactly when it is palindromic and \(R(n)=4\).
For a chosen cube \(b^3\), the equation \(n=a^2+b^3\) is equivalent to
$$a^2=n-b^3.$$
Thus every admissible \(b\) produces at most one possible \(a\): we only have to test whether \(n-b^3\) is a perfect square. Since \(a\ge2\), the remainder must be at least \(4\), so the cube loop stops at \(b^3\le n-4\).
This explains the smallest admissible value as well:
$$2^2+2^3=4+8=12.$$
Therefore the implementation skips all palindromes below \(12\), and for every later candidate it performs exact integer-square-root checks.
A brute-force scan over all integers wastes almost all of its effort on numbers that are not palindromes. The code instead generates only palindromes. The number of \(d\)-digit palindromes is
$$9\cdot 10^{\lceil d/2\rceil-1},$$
whereas the number of all \(d\)-digit integers is \(9\cdot 10^{d-1}\). So the search space shrinks from size about \(10^d\) to size about \(10^{d/2}\), which is the main practical speedup.
If \(p\) is a \(k\)-digit prefix and \(\operatorname{rev}(p)\) denotes decimal digit reversal, then every palindrome is obtained by mirroring that prefix. The code uses
$$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$$
$$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right).$$
The odd-length formula mirrors everything except the center digit, so no digit is duplicated. By iterating lengths increasingly and prefixes increasingly, palindromes are produced in strictly increasing numeric order. Hence the first five accepted values are automatically the five smallest answers.
As the current palindrome grows, larger cubes become relevant. Recomputing \(2^3,3^3,4^3,\dots\) from scratch for each candidate would be wasteful, so the program stores all previously needed cubes in a list and extends that list only when necessary.
In other words, once \(b^3\) has been generated, it is reused for all future palindromes. This keeps the inner loop simple: iterate through cached cubes, stop when \(b^3+4>n\), and test whether the remainder is a square.
The C++ checkpoint uses the palindrome \(5229225\), because it has exactly four valid representations:
$$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3.$$
So \(R(5229225)=4\), which makes it a valid hit.
Exhaustiveness. Every positive decimal palindrome has a unique length and a unique left prefix. The mirroring formulas generate that palindrome exactly once.
Ordering. All \(d\)-digit palindromes are smaller than every \((d+1)\)-digit palindrome, and within one fixed length, increasing the prefix increases the palindrome. So the enumeration order is ascending.
Exact counting. For each admissible \(b\), the value \(n-b^3\) determines \(a\) uniquely if and only if it is a perfect square. Thus counting square remainders is exactly the same as counting pairs \((a,b)\).
Combining these facts shows that the algorithm returns precisely the first five palindromic integers with \(R(n)=4\).
The helper make_palindrome builds candidates via prefix mirroring. ensure_cubes_up_to grows the cache of cubes just far enough for the current palindrome. Then count_representations loops over cached cubes and uses an integer square root to test whether the remainder is a square. The main loop increases the palindrome length until five hits have been collected. The Python and Java versions implement the same logic, and the C++ version additionally cross-checks the optimized search against brute force on a small limit.
If \(N\) is the largest palindrome inspected, then the number of palindromic candidates up to \(N\) is \(\Theta(\sqrt{N})\), because a palindrome is determined by roughly half of its digits. For one candidate \(n\), representation counting tests cubes up to \(n^{1/3}\), so it costs \(O(n^{1/3})\) time with \(O(1)\) work per cube. Therefore the total search cost up to horizon \(N\) is bounded by
$$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6}).$$
The memory usage is \(O(N^{1/3})\) for the cached cubes. This is much better than scanning all integers up to \(N\), which would already require \(\Theta(N)\) candidate checks before counting representations.
Gesucht sind palindromische ganze Zahlen \(n\), die sich auf genau vier verschiedene Arten in der Form
$$n=a^2+b^3,\qquad a,b \gt 1$$
darstellen lassen. Das Programm soll die fünf kleinsten solchen Palindrome finden und summieren; der endgültige Project-Euler-Wert wird hier bewusst nicht angegeben.
Für ein festes \(n\) definieren wir die Darstellungsanzahl
$$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}.$$
Ein Kandidat wird genau dann akzeptiert, wenn er palindromisch ist und \(R(n)=4\) gilt.
Für ein vorgegebenes Kubikzahlglied \(b^3\) ist die Gleichung \(n=a^2+b^3\) äquivalent zu
$$a^2=n-b^3.$$
Damit liefert jedes zulässige \(b\) höchstens ein mögliches \(a\): Man muss nur prüfen, ob \(n-b^3\) ein vollkommenes Quadrat ist. Wegen \(a\ge2\) muss der Rest mindestens \(4\) sein; deshalb genügt die Schleife über \(b^3\le n-4\).
Darum ist auch der kleinste zulässige Wert
$$2^2+2^3=4+8=12.$$
Folglich überspringt die Implementierung alle Palindrome unter \(12\) und arbeitet danach nur noch mit exakten Ganzzahlwurzel-Tests.
Ein Vollscan über alle ganzen Zahlen verschwendet fast alle Tests an Nicht-Palindromen. Der Code erzeugt deshalb direkt nur Palindrome. Die Anzahl der \(d\)-stelligen Palindrome beträgt
$$9\cdot 10^{\lceil d/2\rceil-1},$$
während es insgesamt \(9\cdot 10^{d-1}\) \(d\)-stellige Zahlen gibt. Der Suchraum schrumpft also von ungefähr \(10^d\) auf ungefähr \(10^{d/2}\); genau das liefert den praktischen Geschwindigkeitsgewinn.
Ist \(p\) ein \(k\)-stelliges Präfix und \(\operatorname{rev}(p)\) die Ziffernumkehrung, dann lässt sich jedes Palindrom durch Spiegelung dieses Präfixes konstruieren. Verwendet werden
$$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$$
$$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right).$$
Bei ungerader Länge wird die mittlere Ziffer nicht doppelt gespiegelt. Wenn man Längen aufsteigend und Präfixe aufsteigend durchläuft, entstehen die Palindrome in streng wachsender Reihenfolge. Damit sind die ersten fünf Treffer automatisch die fünf kleinsten Lösungen.
Mit wachsendem Kandidaten \(n\) werden größere Kubikzahlen relevant. Statt \(2^3,3^3,4^3,\dots\) für jedes \(n\) neu auszurechnen, speichert das Programm alle bisher benötigten Kubikzahlen in einer Liste und erweitert diese nur dann, wenn es nötig ist.
Sobald also ein Wert \(b^3\) erzeugt wurde, wird er für alle späteren Palindrome wiederverwendet. Die innere Prüfung lautet dann nur noch: durchlaufe die gecachten Kubikzahlen, stoppe bei \(b^3+4>n\), und teste, ob der Rest ein Quadrat ist.
Der C++-Checkpoint benutzt das Palindrom \(5229225\), weil es genau vier gültige Darstellungen besitzt:
$$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3.$$
Also gilt \(R(5229225)=4\), daher ist diese Zahl ein gültiger Treffer.
Vollständigkeit. Jedes positive Dezimalpalindrom besitzt genau eine Länge und genau ein linkes Präfix. Die Spiegelungsformeln erzeugen dieses Palindrom genau einmal.
Ordnung. Alle \(d\)-stelligen Palindrome sind kleiner als jedes \((d+1)\)-stellige Palindrom, und bei fester Länge wachsen die Palindrome mit dem Präfix. Die Aufzählung ist also aufsteigend.
Exakte Zählung. Für jedes zulässige \(b\) ist \(a\) genau dann bestimmt, wenn \(n-b^3\) ein Quadrat ist. Das Zählen quadratischer Reste ist daher exakt dasselbe wie das Zählen der Paare \((a,b)\).
Zusammen folgt daraus, dass der Algorithmus genau die ersten fünf palindromischen Zahlen mit \(R(n)=4\) liefert.
Die Hilfsfunktion make_palindrome baut Kandidaten per Präfix-Spiegelung. ensure_cubes_up_to erweitert den Cache der Kubikzahlen gerade so weit, wie es der aktuelle Kandidat verlangt. Anschließend läuft count_representations über diesen Cache und prüft jeden Rest mittels Ganzzahlwurzel auf Quadrateigenschaft. Die Hauptschleife erhöht schrittweise die Palindromlänge, bis fünf Treffer gefunden sind. Python und Java folgen derselben Struktur; die C++-Version verifiziert zusätzlich die Optimierung durch einen Brute-Force-Vergleich auf kleiner Schranke.
Sei \(N\) das größte untersuchte Palindrom. Dann gibt es bis \(N\) nur \(\Theta(\sqrt{N})\) palindromische Kandidaten, weil ein Palindrom durch ungefähr die Hälfte seiner Ziffern bestimmt ist. Für einen Kandidaten \(n\) kostet die Darstellungszählung \(O(n^{1/3})\), da alle Kubikzahlen bis \(n^{1/3}\) geprüft werden. Damit erhält man als obere Schranke für die Gesamtsuche bis \(N\)
$$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6}).$$
Der Speicherverbrauch ist \(O(N^{1/3})\) für den Kubikzahl-Cache. Das ist deutlich besser als ein Vollscan über alle Zahlen bis \(N\), der bereits \(\Theta(N)\) Kandidatenprüfungen kosten würde.
Aranan sayılar, tam olarak dört farklı şekilde
$$n=a^2+b^3,\qquad a,b \gt 1$$
biçiminde yazılabilen palindromik tamsayılardır. Çözüm, bu tür palindromların en küçük beş tanesini bulup toplamlarını alır; nihai Project Euler cevabı burada bilerek verilmez.
Sabit bir \(n\) için temsil sayısını
$$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}$$
şeklinde tanımlayalım. Bir aday ancak palindrom ise ve \(R(n)=4\) sağlanıyorsa kabul edilir.
Seçilen bir küp \(b^3\) için \(n=a^2+b^3\) eşitliği doğrudan
$$a^2=n-b^3$$
biçimine iner. Yani her uygun \(b\) en fazla bir tane \(a\) adayı üretir; yapılacak iş yalnızca \(n-b^3\)'ün tam kare olup olmadığını test etmektir. \(a\ge2\) koşulu nedeniyle kalan değer en az \(4\) olmalıdır; bu yüzden küp döngüsü \(b^3\le n-4\) sınırında durur.
Bu aynı zamanda en küçük uygun değeri de açıklar:
$$2^2+2^3=4+8=12.$$
Dolayısıyla kod, \(12\)'den küçük tüm palindromları geçer ve geri kalan her aday için tam sayı karekökü ile kesin tam kare testi yapar.
Tüm tamsayıları taramak, testlerin neredeyse tamamını palindrom olmayan sayılara harcamak demektir. Bunun yerine kod yalnızca palindrom üretir. \(d\) basamaklı palindrom sayısı
$$9\cdot 10^{\lceil d/2\rceil-1}$$
iken, tüm \(d\) basamaklı sayıların sayısı \(9\cdot 10^{d-1}\)'dir. Yani arama uzayı yaklaşık \(10^d\) ölçeğinden \(10^{d/2}\) ölçeğine iner; pratik hızlanmanın ana sebebi budur.
\(p\) bir \(k\) basamaklı önek, \(\operatorname{rev}(p)\) ise basamaklarını ters çevirme işlemi olsun. Her palindrom, bu öneğin yansıtılmasıyla üretilebilir. Kod şu formülleri kullanır:
$$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$$
$$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right).$$
Tek uzunluklu durumda orta basamak iki kez eklenmez. Uzunlukları artan sırada, her uzunluk içinde de önekleri artan sırada gezmek sayıları sıkı biçimde artan sırayla üretir. Böylece bulunan ilk beş kabul, otomatik olarak en küçük beş çözümdür.
Aday palindrom büyüdükçe daha büyük küpler de geçerli hale gelir. Her aday için \(2^3,3^3,4^3,\dots\) değerlerini baştan üretmek yerine program bunları bir listede tutar ve yalnızca gerektiğinde listeye yeni küpler ekler.
Böylece bir kez üretilen \(b^3\) değeri, sonraki tüm palindromlarda yeniden kullanılır. İç döngünün mantığı sadeleşir: önbellekteki küpleri sırayla dolaş, \(b^3+4>n\) olunca dur, kalan değerin tam kare olup olmadığını sınayarak temsilleri say.
C++ doğrulama adımı, \(5229225\) palindromunu kullanır; çünkü bu sayı tam olarak dört farklı gösterime sahiptir:
$$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3.$$
Dolayısıyla \(R(5229225)=4\) ve sayı kabul edilir.
Tamlık. Her pozitif onluk palindromun tek bir uzunluğu ve tek bir sol öneği vardır. Yansıtma formülleri o palindromu tam bir kez üretir.
Sıralama. Tüm \(d\) basamaklı palindromlar, her \((d+1)\) basamaklı palindromdan küçüktür. Sabit uzunlukta ise önek büyüdükçe palindrom da büyür. Bu nedenle üretim sırası artandır.
Kesin temsil sayımı. Her uygun \(b\) için \(n-b^3\) değeri tam kareyse \(a\) tekil olarak belirlenir. O halde tam kare kalanları saymak ile \((a,b)\) çiftlerini saymak tamamen aynı iştir.
Bu üç gözlem birlikte, algoritmanın \(R(n)=4\) koşulunu sağlayan en küçük beş palindromu tam olarak döndürdüğünü gösterir.
make_palindrome yardımcı fonksiyonu adayları önek yansıtma ile üretir. ensure_cubes_up_to, geçerli küp listesini mevcut palindrom için yeterli olacak kadar genişletir. Ardından count_representations, bu listedeki küpler üzerinde gezip tam sayı karekökü yardımıyla tam kare testi yapar. Ana döngü palindrom uzunluğunu artırarak beş kabul değeri toplayana kadar devam eder. Python ve Java sürümleri aynı yapıyı izler; C++ sürümü ek olarak küçük bir üst sınırda kaba kuvvetle çapraz kontrol de yapar.
\(N\), incelenen en büyük palindrom olsun. \(N\)'ye kadar olan palindrom aday sayısı, sayının yaklaşık yarı basamağı tarafından belirlenmeleri nedeniyle \(\Theta(\sqrt{N})\)'dir. Tek bir aday \(n\) için temsil sayımı, \(n^{1/3}\)'e kadar tüm küpleri denediği için \(O(n^{1/3})\) zamanda yapılır. Böylece \(N\) ufkuna kadar toplam arama maliyeti
$$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6})$$
ile sınırlanır. Bellek maliyeti küp önbelleği için \(O(N^{1/3})\)'tür. Bu, \(N\)'ye kadar tüm tamsayıları tarayan yaklaşımın en az \(\Theta(N)\) aday kontrolü gerektirmesine göre belirgin biçimde daha iyidir.
Buscamos enteros palindrómicos \(n\) que tengan exactamente cuatro representaciones distintas de la forma
$$n=a^2+b^3,\qquad a,b \gt 1.$$
El programa debe hallar los cinco menores palíndromos con esa propiedad y sumarlos, aunque el valor final de Project Euler se omite deliberadamente aquí.
Para un \(n\) fijo, definimos el número de representaciones
$$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}.$$
Un candidato se acepta si y solo si es palíndromo y cumple \(R(n)=4\).
Si fijamos un cubo \(b^3\), la ecuación \(n=a^2+b^3\) se reduce a
$$a^2=n-b^3.$$
Por tanto, cada \(b\) admisible produce como mucho un valor posible de \(a\): basta comprobar si \(n-b^3\) es un cuadrado perfecto. Como \(a\ge2\), el resto debe ser al menos \(4\), así que el bucle de cubos se detiene en \(b^3\le n-4\).
Esto también explica el menor valor posible:
$$2^2+2^3=4+8=12.$$
Así, la implementación descarta todos los palíndromos menores que \(12\) y, para cada candidato restante, usa una raíz cuadrada entera para verificar de forma exacta si hay cuadrado perfecto.
Un barrido ingenuo sobre todos los enteros desperdicia casi todo su trabajo en números que no son palíndromos. El código invierte la idea y genera solo palíndromos. El número de palíndromos de \(d\) cifras es
$$9\cdot 10^{\lceil d/2\rceil-1},$$
mientras que el número total de enteros de \(d\) cifras es \(9\cdot 10^{d-1}\). Por eso el espacio de búsqueda baja de una escala cercana a \(10^d\) a una cercana a \(10^{d/2}\).
Si \(p\) es un prefijo de \(k\) cifras y \(\operatorname{rev}(p)\) denota su reverso decimal, todo palíndromo puede construirse reflejando ese prefijo. El código usa
$$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$$
$$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right).$$
En longitud impar no se duplica la cifra central. Recorriendo primero las longitudes y luego los prefijos en orden creciente, los palíndromos salen en orden estrictamente ascendente. Por eso los cinco primeros aceptados son exactamente las cinco soluciones mínimas.
A medida que el palíndromo actual crece, también entran en juego cubos mayores. En lugar de recomputar \(2^3,3^3,4^3,\dots\) para cada candidato, el programa guarda todos los cubos ya necesarios en una lista y solo amplía esa lista cuando hace falta.
Una vez generado un valor \(b^3\), se reutiliza para todos los palíndromos posteriores. Así el bucle interno solo recorre la caché, se detiene cuando \(b^3+4>n\) y prueba si el resto es cuadrado perfecto.
La comprobación de la versión C++ usa el palíndromo \(5229225\), porque posee exactamente cuatro representaciones válidas:
$$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3.$$
Por lo tanto, \(R(5229225)=4\).
Exhaustividad. Todo palíndromo decimal positivo tiene una longitud única y un prefijo izquierdo único. Las fórmulas de reflexión lo generan exactamente una vez.
Orden. Todo palíndromo de \(d\) cifras es menor que cualquier palíndromo de \(d+1\) cifras, y dentro de una misma longitud el valor crece con el prefijo. La enumeración es ascendente.
Conteo exacto. Para cada \(b\) admisible, el valor \(n-b^3\) determina un único \(a\) si y solo si es cuadrado perfecto. Así, contar restos cuadrados equivale exactamente a contar pares \((a,b)\).
De estas tres observaciones se sigue que el algoritmo devuelve precisamente los cinco menores palíndromos con \(R(n)=4\).
La función auxiliar make_palindrome construye candidatos por reflexión del prefijo. ensure_cubes_up_to amplía la caché de cubos solo hasta donde exige el palíndromo actual. Luego count_representations recorre esa caché y usa raíz cuadrada entera para comprobar si el resto es un cuadrado perfecto. El bucle principal aumenta la longitud del palíndromo hasta reunir cinco aciertos. Python y Java siguen la misma estructura, y la versión C++ además compara la búsqueda optimizada con fuerza bruta en un límite pequeño.
Si \(N\) es el mayor palíndromo inspeccionado, entonces el número de candidatos palindrómicos hasta \(N\) es \(\Theta(\sqrt{N})\), porque un palíndromo queda determinado por aproximadamente la mitad de sus cifras. Para un candidato \(n\), contar representaciones cuesta \(O(n^{1/3})\), ya que se prueban cubos hasta ese orden. Por tanto, el coste total de búsqueda hasta el umbral \(N\) queda acotado por
$$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6}).$$
La memoria es \(O(N^{1/3})\) por la caché de cubos. Esto mejora claramente frente a escanear todos los enteros hasta \(N\), lo que ya exigiría \(\Theta(N)\) verificaciones de candidatos.
我们要寻找满足下式且恰好有四种不同表示的回文整数 \(n\)：
$$n=a^2+b^3,\qquad a,b \gt 1.$$
程序需要找到最小的五个这样的回文数并求和，但这里仍然不直接给出最终的 Project Euler 答案。
对固定的 \(n\)，定义表示个数
$$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}$$
只有当 \(n\) 是回文数且 \(R(n)=4\) 时，这个候选值才被接受。
固定一个立方项 \(b^3\) 后，方程 \(n=a^2+b^3\) 等价于
$$a^2=n-b^3$$
因此每个可行的 \(b\) 至多对应一个 \(a\)：只需判断 \(n-b^3\) 是否为完全平方数即可。由于 \(a\ge2\)，剩余项至少要是 \(4\)，所以只需要检查 \(b^3\le n-4\)。
这也解释了最小可行值：
$$2^2+2^3=4+8=12$$
所以实现中会直接跳过所有小于 \(12\) 的回文数，并对之后的每个候选值做精确的整数平方根判定。
如果按所有整数顺序扫描，绝大多数工作都会浪费在非回文数上。代码反过来只生成回文候选。\(d\) 位回文数的数量是
$$9\cdot 10^{\lceil d/2\rceil-1},$$
而全部 \(d\) 位整数的数量是 \(9\cdot 10^{d-1}\)。也就是说，搜索规模从接近 \(10^d\) 降到接近 \(10^{d/2}\)，这是算法实际加速的核心原因。
设 \(p\) 是一个 \(k\) 位前缀，\(\operatorname{rev}(p)\) 表示它的十进制反转。所有回文数都可以通过镜像这个前缀得到：
$$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$$
$$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right)$$
奇数长度时不会重复中间那一位。按长度递增、再按前缀递增的顺序枚举时，得到的回文数本身就是严格递增的，因此找到的前五个命中值一定就是最小的五个答案。
随着当前回文数变大，更大的立方也会变得可用。若对每个候选值都重新计算 \(2^3,3^3,4^3,\dots\)，会造成大量重复工作。程序因此维护一个立方列表，只在需要时向后追加新立方。
一旦某个 \(b^3\) 被生成，它就会被之后所有更大的回文数复用。内层逻辑因此很直接：遍历缓存立方，若 \(b^3+4>n\) 就停止，否则检查剩余项是否为完全平方数。
C++ 版本中的检查点使用回文数 \(5229225\)，因为它恰好有四种有效表示：
$$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3$$
因此 \(R(5229225)=4\)。
完备性。 每个正十进制回文数都有唯一的长度和唯一的左半前缀，镜像公式会且只会生成它一次。
有序性。 所有 \(d\) 位回文数都小于任何 \(d+1\) 位回文数；在固定长度内，前缀越大，生成的回文数也越大。因此枚举顺序是递增的。
计数精确性。 对每个可行的 \(b\)，若 \(n-b^3\) 是完全平方数，就唯一确定一个 \(a\)。所以“统计平方剩余项”与“统计所有 \((a,b)\) 解对”完全等价。
综合这三点，算法确实返回满足 \(R(n)=4\) 的最小五个回文整数。
make_palindrome 负责按前缀镜像生成候选值；ensure_cubes_up_to 只把立方缓存扩展到当前回文数所需的范围；count_representations 遍历这些立方并通过整数平方根判断剩余项是否为完全平方数。主循环不断增加回文长度，直到收集到五个命中值。Python 和 Java 版本遵循同样的结构，C++ 版本还额外在小范围上用暴力法做交叉验证。
设 \(N\) 是检查到的最大回文数。由于一个回文数只由大约一半的数字决定，所以不超过 \(N\) 的回文候选个数是 \(\Theta(\sqrt{N})\)。对单个候选 \(n\)，表示计数要检查到 \(n^{1/3}\) 量级的立方，因此时间为 \(O(n^{1/3})\)。于是搜索到上界 \(N\) 的总成本满足
$$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6})$$
空间复杂度为 \(O(N^{1/3})\)，主要来自立方缓存。相比之下，如果扫描所有不超过 \(N\) 的整数，仅候选检查本身就需要 \(\Theta(N)\) 步。
Нужно найти палиндромные целые числа \(n\), которые имеют ровно четыре различных представления вида
$$n=a^2+b^3,\qquad a,b \gt 1.$$
Программа должна взять пять наименьших таких палиндромов и просуммировать их, но окончательный ответ Project Euler здесь намеренно не приводится.
Для фиксированного \(n\) введём число представлений
$$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}.$$
Кандидат принимается тогда и только тогда, когда он является палиндромом и выполняется \(R(n)=4\).
Если куб \(b^3\) уже выбран, уравнение \(n=a^2+b^3\) сводится к
$$a^2=n-b^3.$$
Значит, для каждого допустимого \(b\) существует не более одного кандидата \(a\): нужно лишь проверить, является ли \(n-b^3\) точным квадратом. Так как \(a\ge2\), остаток должен быть не меньше \(4\), поэтому достаточно перебирать \(b^3\le n-4\).
Отсюда же виден минимальный допустимый случай:
$$2^2+2^3=4+8=12.$$
Именно поэтому код сразу пропускает все палиндромы меньше \(12\), а для остальных использует точную проверку через целочисленный квадратный корень.
Полный перебор всех целых чисел тратит почти всё время на числа, которые вообще не являются палиндромами. Поэтому программа генерирует только палиндромные кандидаты. Число \(d\)-значных палиндромов равно
$$9\cdot 10^{\lceil d/2\rceil-1},$$
тогда как число всех \(d\)-значных целых равно \(9\cdot 10^{d-1}\). Значит, поисковое пространство сокращается примерно с масштаба \(10^d\) до масштаба \(10^{d/2}\).
Пусть \(p\) — \(k\)-значный префикс, а \(\operatorname{rev}(p)\) — запись его цифр в обратном порядке. Тогда любой палиндром строится отражением этого префикса:
$$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$$
$$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right).$$
В нечётной длине центральная цифра не дублируется. Если идти по длинам по возрастанию и внутри каждой длины увеличивать префикс, палиндромы будут порождаться строго в возрастающем порядке. Поэтому первые пять найденных значений автоматически являются пятью наименьшими решениями.
Когда текущий палиндром растёт, становятся нужны и большие кубы. Повторно вычислять \(2^3,3^3,4^3,\dots\) для каждого кандидата невыгодно, поэтому программа хранит все уже нужные кубы в массиве и дополняет его только при необходимости.
Как только значение \(b^3\) однажды построено, оно повторно используется для всех следующих палиндромов. Внутренний цикл поэтому прост: пройти по кэшу кубов, остановиться при \(b^3+4>n\), проверить, является ли остаток точным квадратом.
В контрольной проверке C++ используется палиндром \(5229225\), потому что у него ровно четыре допустимых представления:
$$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3.$$
Следовательно, \(R(5229225)=4\).
Полнота. У каждого положительного десятичного палиндрома есть единственная длина и единственный левый префикс. Формулы зеркалирования порождают его ровно один раз.
Порядок. Любой \(d\)-значный палиндром меньше любого \((d+1)\)-значного, а при фиксированной длине увеличение префикса увеличивает и сам палиндром. Значит, перечисление идёт по возрастанию.
Точный подсчёт. Для каждого допустимого \(b\) значение \(n-b^3\) задаёт \(a\) однозначно тогда и только тогда, когда это квадрат. Поэтому подсчёт квадратных остатков в точности совпадает с подсчётом пар \((a,b)\).
Из этих трёх фактов следует, что алгоритм действительно возвращает пять наименьших палиндромов с условием \(R(n)=4\).
Функция make_palindrome строит кандидаты зеркалированием префикса. ensure_cubes_up_to расширяет список кубов ровно до нужного диапазона для текущего палиндрома. Затем count_representations проходит по этому списку и через целочисленный квадратный корень проверяет, является ли остаток квадратом. Главный цикл увеличивает длину палиндромов, пока не найдёт пять подходящих значений. Версии на Python и Java повторяют ту же структуру; в C++ есть дополнительная сверка с грубой силой на малом пределе.
Пусть \(N\) — наибольший проверенный палиндром. Тогда число палиндромных кандидатов до \(N\) равно \(\Theta(\sqrt{N})\), потому что палиндром определяется примерно половиной своих цифр. Для одного кандидата \(n\) подсчёт представлений стоит \(O(n^{1/3})\), поскольку проверяются кубы до этого масштаба. Значит, полная стоимость поиска до уровня \(N\) ограничена сверху выражением
$$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6}).$$
Память равна \(O(N^{1/3})\) из-за кэша кубов. Это существенно лучше полного перебора всех чисел до \(N\), который уже сам по себе требует \(\Theta(N)\) проверок кандидатов.
نبحث عن أعداد متناظرة \(n\) لها بالضبط أربع تمثيلات مختلفة من الشكل
$$n=a^2+b^3,\qquad a,b \gt 1.$$
المطلوب هو إيجاد أصغر خمسة أعداد متناظرة بهذه الخاصية ثم جمعها، لكن الجواب النهائي لمسألة Project Euler غير معروض هنا عمدًا.
لعدد ثابت \(n\) نعرّف عدد التمثيلات بالصيغة
$$R(n)=\#\{(a,b)\in\mathbb{Z}_{\ge2}^2:\ n=a^2+b^3\}.$$
يُقبل المرشح فقط إذا كان متناظرًا ويحقق \(R(n)=4\).
إذا ثبتنا مكعبًا \(b^3\)، فإن المعادلة \(n=a^2+b^3\) تكافئ مباشرة
$$a^2=n-b^3.$$
أي إن كل قيمة مسموحة لـ \(b\) تعطي على الأكثر قيمة واحدة ممكنة لـ \(a\)، ولذلك يكفي اختبار ما إذا كان \(n-b^3\) مربعًا كاملًا. وبما أن \(a\ge2\)، فلا بد أن يكون الباقي على الأقل \(4\)، ولهذا نتوقف عند الشرط \(b^3\le n-4\).
وهذا يفسر أيضًا أصغر قيمة ممكنة:
$$2^2+2^3=4+8=12.$$
إذًا تتجاوز الخوارزمية كل الأعداد المتناظرة الأصغر من \(12\)، ثم تستخدم جذرًا تربيعيًا صحيحًا لاختبار المربعات الكاملة بدقة تامة.
المسح المباشر لكل الأعداد الصحيحة يهدر معظم العمل على أعداد ليست متناظرة أصلًا. لذلك يعكس البرنامج الفكرة ويولّد المتناظرات فقط. عدد الأعداد المتناظرة ذات \(d\) خانات هو
$$9\cdot 10^{\lceil d/2\rceil-1},$$
بينما عدد جميع الأعداد ذات \(d\) خانات هو \(9\cdot 10^{d-1}\). وهكذا ينخفض مجال البحث من رتبة تقارب \(10^d\) إلى رتبة تقارب \(10^{d/2}\).
إذا كانت \(p\) بادئة من \(k\) خانات و\(\operatorname{rev}(p)\) تمثل قلب الخانات ترتيبًا، فإن كل عدد متناظر يمكن بناؤه عبر عكس هذه البادئة. يستعمل الكود الصيغتين:
$$\operatorname{pal}_{\mathrm{even}}(p)=p\cdot 10^k+\operatorname{rev}(p),$$
$$\operatorname{pal}_{\mathrm{odd}}(p)=p\cdot 10^{k-1}+\operatorname{rev}\!\left(\left\lfloor\frac{p}{10}\right\rfloor\right).$$
في الطول الفردي لا تتكرر الخانة الوسطى. وعند المرور على الأطوال تصاعديًا ثم على البوادئ تصاعديًا داخل كل طول، تُنتَج المتناظرات بترتيب عددي متزايد صارم، ولذلك تكون أول خمس قيم مقبولة هي بالفعل أصغر خمس حلول.
كلما كبر المرشح الحالي، أصبحت مكعبات أكبر قابلة للاستخدام. وإعادة حساب \(2^3,3^3,4^3,\dots\) من الصفر لكل مرشح فكرة مكلفة، لذا يحتفظ البرنامج بقائمة للمكعبات التي تم توليدها سابقًا، ولا يضيف إليها إلا عند الحاجة.
بمجرد توليد قيمة \(b^3\) مرة واحدة، يعاد استخدامها مع كل المتناظرات اللاحقة. وهكذا تصبح الحلقة الداخلية بسيطة: سر عبر المكعبات المخزنة، وتوقف عندما يتحقق \(b^3+4>n\)، ثم اختبر هل الباقي مربع كامل.
تستخدم نقطة التحقق في نسخة C++ العدد المتناظر \(5229225\) لأنه يملك بالضبط أربع تمثيلات صحيحة:
$$5229225=2285^2+20^3=2223^2+66^3=1810^2+125^3=1197^2+156^3.$$
وبالتالي \(R(5229225)=4\).
الشمول. لكل عدد متناظر عشري موجب طول وحيد وبادئة يسرى وحيدة، وصيغتا الانعكاس تولدانه مرة واحدة بالضبط.
الترتيب. كل متناظر ذي \(d\) خانات أصغر من أي متناظر ذي \(d+1\) خانات، وداخل الطول الثابت تكبر القيمة بزيادة البادئة. إذًا التوليد يتم تصاعديًا.
العدّ الدقيق. لكل \(b\) مسموح، يكون \(a\) محددًا على نحو وحيد إذا وفقط إذا كان \(n-b^3\) مربعًا كاملًا. لذا فإن عدّ البواقي المربعة يكافئ تمامًا عدّ الأزواج \((a,b)\).
ومن ثم يعيد هذا الأسلوب بالضبط أصغر خمسة أعداد متناظرة تحقق \(R(n)=4\).
الدالة المساعدة make_palindrome تبني المرشحين عبر انعكاس البادئة. والدالة ensure_cubes_up_to توسع قائمة المكعبات إلى الحد الضروري فقط للمرشح الحالي. بعد ذلك تمر count_representations على هذه القائمة وتستخدم جذرًا تربيعيًا صحيحًا للتحقق من كون الباقي مربعًا كاملًا. الحلقة الرئيسية تزيد طول المتناظر حتى تجمع خمس قيم مقبولة. وتستخدم نسختا Python وJava البنية نفسها، بينما تضيف نسخة C++ مقارنة تحقق مع brute force على حد صغير.
إذا كان \(N\) هو أكبر عدد متناظر جرى فحصه، فإن عدد المرشحين المتناظرين حتى \(N\) يساوي \(\Theta(\sqrt{N})\)، لأن العدد المتناظر يتحدد تقريبًا بنصف خاناته. أما حساب عدد التمثيلات لمرشح واحد \(n\) فيكلف \(O(n^{1/3})\)، لأننا نفحص جميع المكعبات حتى هذا الحجم. لذلك تكون كلفة البحث الكلية حتى الأفق \(N\) محصورة بـ
$$O\!\left(\sqrt{N}\,N^{1/3}\right)=O(N^{5/6}).$$
واستهلاك الذاكرة هو \(O(N^{1/3})\) بسبب قائمة المكعبات المخزنة. وهذا أفضل بكثير من مسح كل الأعداد حتى \(N\)، لأن ذلك يتطلب أصلًا \(\Theta(N)\) فحصًا للمرشحين.