For each integer \(1 \le n < 10{,}000\), repeatedly apply the decimal reverse-and-add map. If none of the first 50 generated values is a palindrome, the starting number is counted as a Lychrel number for the purpose of this problem. The task is therefore a finite counting problem: determine how many starting values stay non-palindromic for all 50 prescribed steps.
The important subtlety is that this definition is operational rather than absolute. Some starting values, such as 196, are famous unresolved cases in the unrestricted reverse-and-add process. Here we do not need to decide whether they are truly Lychrel in an infinite sense; we only need to test the first 50 iterations exactly.
Let \(R(x)\) denote the decimal reversal of \(x\). If \(x\) has digits \(a_{d-1}a_{d-2}\dots a_1a_0\), then
$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i},$$
with the usual convention that leading zeros in the reversed digit string disappear numerically. Starting from \(x_0=n\), the process is
$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$
We write \(P(x)\iff x=R(x)\) for the palindrome predicate. A starting value is counted precisely when
$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$
Each starting number generates a deterministic orbit under the map \(x\mapsto x+R(x)\). Because the Project Euler condition only asks about the first 50 images, there is no need for probabilistic heuristics or conjectures about infinite behavior. The problem reduces to examining 9,999 independent trajectories inside the finite horizon \(t\le 50\).
Formally, the set being counted is
$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}.$$
This formulation matches the implementations exactly: every number below \(10^4\) is tested separately, and the moment a palindrome appears the trajectory is removed from the count.
The palindrome test is applied after a reverse-and-add step, not to the original input. That detail matters. A number such as \(121\) is already palindromic, but the relevant sequence is
$$121 \to 121+121=242,$$
so it is still processed through one iteration and then succeeds immediately. The decision rule depends on the generated values \(x_1,x_2,\dots\), not on \(x_0\) itself.
If \(x\) has \(d\) decimal digits, then \(x<10^d\) and also \(R(x)<10^d\). Hence
$$x+R(x)<2\cdot 10^d<10^{d+1}.$$
So a single reverse-and-add step can increase the digit count by at most one. Since every input in this problem has at most four digits, after at most 50 steps every intermediate value has at most \(4+50=54\) digits.
This bound explains why manual decimal-string arithmetic is sufficient. The values can exceed native 64-bit types, but they never become remotely too large for a carry-based string implementation.
The standard non-Lychrel example from the statement is
$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$
A palindrome appears at the third generated value, so 349 is excluded from \(\mathcal{L}_{50}\).
A simpler checkpoint is \(47\):
$$47 \to 47+74=121.$$
That becomes palindromic immediately. By contrast, 196 begins
$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$
and does not reach a palindrome within the first 50 iterations. Therefore it is counted by the problem's finite rule, regardless of the unresolved infinite version of the question.
The C++, Python, and Java implementations all keep the current iterate as a decimal string. Reversal is obtained by reversing that string, and addition is performed digit by digit from right to left with an explicit carry. This is ordinary schoolbook addition, and it avoids any dependence on big-integer libraries.
Palindrome detection is a direct two-ended comparison on the current string. Because all intermediate values stay within the 54-digit bound above, this representation is simple, portable, and fully adequate in all three languages.
For a single starting value, the implementation repeats the same loop at most 50 times: reverse, add, test for palindromicity, and stop early if a palindrome appears. A starting value is counted only if the loop survives all 50 rounds without success.
After that, the outer routine applies the test to every integer from 1 up to 9999 and counts the survivors. The default parameters match the Project Euler statement, but the programs also allow the upper limit and the iteration cap to be changed from the command line. Before printing the final count, they verify familiar examples such as 47 and 349 to confirm that the rule has been implemented correctly.
Let \(L=9999\), let \(S=50\), and let \(D\) be the maximum number of digits seen during the run. Each iteration performs one reversal, one addition with carry, and one palindrome check, all linear in the current digit length. Therefore the running time is
$$O(LSD).$$
For Problem 55, the digit-growth bound gives \(D\le 54\), so the total work is only on the order of tens of millions of character-level operations. Space usage is \(O(D)\), since at any moment the code stores only the current decimal string, its reversal, and a small amount of loop state.
Für jede ganze Zahl \(1 \le n < 10{,}000\) wird wiederholt der dezimale Reverse-and-Add-Schritt ausgeführt. Wenn unter den ersten 50 erzeugten Werten kein Palindrom erscheint, wird der Startwert im Sinn dieser Aufgabe als Lychrel-Zahl gezählt. Gesucht ist also die Anzahl der Startwerte, die während aller 50 vorgeschriebenen Schritte nicht palindromisch werden.
Wichtig ist, dass diese Definition operativ und nicht absolut ist. Manche Startwerte wie 196 sind im unbegrenzten Reverse-and-Add-Prozess berühmte offene Fälle. Hier muss nicht entschieden werden, ob sie im unendlichen Sinn wirklich Lychrel sind; geprüft werden nur die ersten 50 Iterationen.
Sei \(R(x)\) die Dezimalumkehrung von \(x\). Hat \(x\) die Ziffern \(a_{d-1}a_{d-2}\dots a_1a_0\), dann gilt
$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i},$$
wobei führende Nullen der umgekehrten Ziffernfolge numerisch einfach verschwinden. Mit \(x_0=n\) lautet die Iteration
$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$
Für das Palindrom-Prädikat schreiben wir \(P(x)\iff x=R(x)\). Ein Startwert wird genau dann gezählt, wenn
$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$
Jeder Startwert erzeugt unter der Abbildung \(x\mapsto x+R(x)\) eine deterministische Bahn. Da die Project-Euler-Bedingung nur nach den ersten 50 Bildern fragt, braucht man weder probabilistische Heuristiken noch Vermutungen über das Verhalten im Unendlichen. Das Problem reduziert sich auf 9.999 unabhängige Trajektorien mit dem endlichen Horizont \(t\le 50\).
Formal zählt man die Menge
$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}.$$
Genau das setzen die Implementierungen um: Jede Zahl unter \(10^4\) wird separat geprüft, und sobald ein Palindrom auftaucht, fällt die zugehörige Bahn aus der Zählung heraus.
Der Palindromtest wird nach einem Reverse-and-Add-Schritt angewandt, nicht auf die ursprüngliche Eingabe. Das ist entscheidend. Eine Zahl wie \(121\) ist bereits palindromisch, aber die relevante Folge lautet
$$121 \to 121+121=242,$$
sie wird also trotzdem einmal weiterentwickelt und besteht dann sofort. Die Entscheidungsregel hängt von den erzeugten Werten \(x_1,x_2,\dots\) ab, nicht von \(x_0\) selbst.
Hat \(x\) genau \(d\) Dezimalziffern, dann gilt \(x<10^d\) und ebenso \(R(x)<10^d\). Daher
$$x+R(x)<2\cdot 10^d<10^{d+1}.$$
Ein einzelner Reverse-and-Add-Schritt kann die Ziffernzahl also höchstens um eins erhöhen. Da jede Eingabe in dieser Aufgabe höchstens vierstellig ist, besitzt jeder Zwischenwert nach spätestens 50 Schritten höchstens \(4+50=54\) Ziffern.
Diese Schranke erklärt, warum eine manuelle Dezimal-String-Arithmetik vollkommen ausreicht. Die Werte können 64-Bit-Grenzen überschreiten, werden für die 50-Schritt-Regel aber nie problematisch groß.
Das klassische Nicht-Lychrel-Beispiel aus der Aufgabenstellung ist
$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$
Beim dritten erzeugten Wert erscheint ein Palindrom, also gehört 349 nicht zu \(\mathcal{L}_{50}\).
Ein einfacherer Kontrollfall ist \(47\):
$$47 \to 47+74=121.$$
Das wird sofort palindromisch. Dagegen beginnt 196 mit
$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$
und erreicht in den ersten 50 Iterationen kein Palindrom. Nach der endlichen Regel dieser Aufgabe wird 196 deshalb mitgezählt, unabhängig von der ungelösten unendlichen Version des Problems.
Die C++-, Python- und Java-Implementierungen speichern den aktuellen Iterationswert jeweils als Dezimalzeichenkette. Die Umkehrung entsteht durch Umdrehen dieser Zeichenkette, und die Addition wird mit explizitem Übertrag Ziffer für Ziffer von rechts nach links ausgeführt. Das ist normale schriftliche Addition und vermeidet jede Abhängigkeit von Big-Integer-Bibliotheken.
Die Palindromprüfung erfolgt durch einen Vergleich von beiden Enden der aktuellen Zeichenkette aus. Weil alle Zwischenwerte innerhalb der obigen 54-Ziffern-Schranke bleiben, ist diese Darstellung in allen drei Sprachen einfach und zuverlässig.
Für einen einzelnen Startwert wiederholt die Implementierung höchstens 50-mal dieselbe Schleife: umkehren, addieren, auf Palindromie testen und beim ersten Treffer sofort abbrechen. Ein Startwert wird nur dann gezählt, wenn alle 50 Runden ohne Erfolg durchlaufen werden.
Anschließend wird dieser Test für jede ganze Zahl von 1 bis 9999 ausgeführt und die Zahl der verbleibenden Kandidaten gezählt. Die Standardparameter entsprechen der Project-Euler-Aufgabe, aber Obergrenze und Iterationszahl lassen sich auch über Kommandozeilenargumente verändern. Vor der Endausgabe prüfen die Programme bekannte Beispiele wie 47 und 349, um die korrekte Umsetzung der Regel zu verifizieren.
Sei \(L=9999\), sei \(S=50\), und sei \(D\) die maximale Ziffernzahl während des Laufs. Jede Iteration enthält eine Umkehrung, eine Addition mit Übertrag und einen Palindromtest, also drei lineare Durchläufe über die aktuelle Ziffernlänge. Damit beträgt die Laufzeit
$$O(LSD).$$
Für Problem 55 liefert die Wachstumsabschätzung \(D\le 54\), sodass insgesamt nur Größenordnungen von einigen zehn Millionen Zeichenoperationen anfallen. Der Speicherbedarf ist \(O(D)\), weil zu jedem Zeitpunkt nur die aktuelle Dezimalzeichenkette, ihre Umkehrung und ein kleiner Schleifenzustand gehalten werden.
Her \(1 \le n < 10{,}000\) tam sayısı için ondalık tabanda ters çevirip toplama işlemi tekrar tekrar uygulanır. Oluşan ilk 50 değerin hiçbirinde palindrom görülmezse, bu başlangıç sayısı bu problem açısından Lychrel kabul edilir. Dolayısıyla görev, 50 zorunlu adım boyunca palindrom üretmeyen başlangıçların sayısını bulmaktır.
Buradaki tanım mutlak değil, işlemseldir. 196 gibi bazı sayılar sınırsız ters çevirip toplama sürecinde ünlü açık vakalardır. Bu problemde onların sonsuz süreçte gerçekten Lychrel olup olmadığını kanıtlamamız gerekmez; yalnızca ilk 50 iterasyonu eksiksiz test etmemiz gerekir.
\(R(x)\), \(x\)'in ondalık basamaklarının ters çevrilmesiyle elde edilen sayı olsun. Eğer \(x\), \(a_{d-1}a_{d-2}\dots a_1a_0\) basamaklarına sahipse,
$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i}$$
yazabiliriz. Ters çevirmeden sonra başa gelen sıfırlar sayısal değeri etkilemez. \(x_0=n\) ile başlayınca yineleme
$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0)$$
şeklindedir. Palindrom olma koşulunu \(P(x)\iff x=R(x)\) ile gösterelim. Bir başlangıç sayısı tam olarak şu durumda sayılır:
$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$
Her başlangıç değeri, \(x\mapsto x+R(x)\) dönüşümü altında deterministik bir yörünge üretir. Project Euler koşulu yalnızca ilk 50 görüntüyle ilgilendiği için sonsuz davranış üzerine sezgilere ya da olasılıksal tahminlere ihtiyaç yoktur. Problem, \(t\le 50\) ufku içinde 9.999 bağımsız yörüngenin incelenmesine indirgenir.
Sayılan küme biçimsel olarak
$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}$$
şeklindedir. Uygulamalar tam olarak bunu yapar: \(10^4\)'ten küçük her sayı ayrı ayrı test edilir ve ilk palindrom görüldüğü anda o yörünge sayımdan çıkarılır.
Palindrom testi ilk girişe değil, ters çevirip toplama adımından sonra uygulanır. Bu ayrıntı önemlidir. Örneğin \(121\) zaten palindromdur, ama ilgili dizi
$$121 \to 121+121=242$$
olduğu için yine de bir adım ilerletilir ve sonra hemen başarılı sayılır. Karar kuralı \(x_0\)'a değil, üretilen \(x_1,x_2,\dots\) değerlerine bağlıdır.
Eğer \(x\), \(d\) basamaklıysa \(x<10^d\) ve aynı şekilde \(R(x)<10^d\) olur. Dolayısıyla
$$x+R(x)<2\cdot 10^d<10^{d+1}.$$
Demek ki tek bir ters çevirip toplama adımı basamak sayısını en fazla bir artırabilir. Bu problemde bütün girişler en fazla dört basamaklı olduğundan, 50 adımdan sonra bile her ara değer en fazla \(4+50=54\) basamaklıdır.
Bu sınır, neden elle yazılmış ondalık dizge aritmetiğinin yeterli olduğunu açıklar. Değerler 64 bit sınırını aşabilir, ama 50 adımlık eşik altında taşımalı dizge toplaması için hiçbir zaman aşırı büyümez.
Sorudaki klasik Lychrel olmayan örnek şudur:
$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$
Üçüncü üretilen değerde palindrom ortaya çıkar, dolayısıyla 349, \(\mathcal{L}_{50}\) kümesine girmez.
Daha basit bir kontrol örneği \(47\)'dir:
$$47 \to 47+74=121.$$
Bu sayı hemen palindroma ulaşır. Buna karşılık 196 dizisi
$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$
şeklinde başlar ve ilk 50 iterasyonda palindrom üretmez. Bu yüzden problemin sonlu kuralına göre 196 sayılır; sonsuz sürümün açık olması bunu değiştirmez.
C++, Python ve Java uygulamalarının üçü de o anki iterasyon değerini ondalık bir dizge olarak tutar. Tersini almak için dizge çevrilir, toplama ise sağdan sola doğru açık taşıma kullanılarak basamak basamak yapılır. Bu, normal okul tipi toplamanın aynısıdır ve büyük tamsayı kütüphanelerine bağımlılığı ortadan kaldırır.
Palindrom testi, güncel dizgenin iki ucundan karşılaştırma yapılarak uygulanır. Bütün ara değerler yukarıdaki 54 basamak sınırı içinde kaldığı için bu temsil hem basit hem de üç dilde de tamamen yeterlidir.
Tek bir başlangıç değeri için uygulama en fazla 50 kez aynı döngüyü yürütür: ters çevir, topla, palindromu kontrol et ve palindrom bulunursa erken dur. Yalnızca 50 turun tamamı başarısız geçerse o başlangıç sayılır.
Daha sonra dış döngü 1'den 9999'a kadar her tam sayı için bu testi uygular ve geriye kalanları sayar. Varsayılan parametreler Project Euler ifadesiyle aynıdır; ancak üst sınır ve iterasyon sayısı komut satırından değiştirilebilir. Son sayı yazdırılmadan önce 47 ve 349 gibi bilinen örneklerle kuralın doğru uygulanıp uygulanmadığı kontrol edilir.
\(L=9999\), \(S=50\) ve çalışma sırasında görülen en büyük basamak sayısı \(D\) olsun. Her iterasyonda bir ters çevirme, taşımalı bir toplama ve bir palindrom testi vardır; bunların hepsi güncel basamak uzunluğunda doğrusaldır. Bu yüzden toplam süre
$$O(LSD)$$
olur. Problem 55 için büyüme sınırı \(D\le 54\) verdiğinden, toplam iş yalnızca onlarca milyon karakter düzeyi işlemdir. Bellek kullanımı \(O(D)\)'dir; çünkü aynı anda sadece güncel dizge, onun tersi ve küçük bir döngü durumu saklanır.
Para cada entero \(1 \le n < 10{,}000\), se aplica repetidamente el procedimiento decimal de invertir y sumar. Si ninguno de los primeros 50 valores generados es un palíndromo, el valor inicial se cuenta como número de Lychrel para esta tarea. Por tanto, el objetivo es un conteo finito: determinar cuántos valores iniciales permanecen no palindrómicos durante los 50 pasos exigidos.
La sutileza importante es que esta definición es operativa y no absoluta. Algunos valores iniciales, como 196, son casos famosos no resueltos en el proceso ilimitado de invertir y sumar. Aquí no hace falta decidir si son realmente Lychrel en sentido infinito; sólo hay que comprobar con exactitud las primeras 50 iteraciones.
Sea \(R(x)\) la inversión decimal de \(x\). Si \(x\) tiene cifras \(a_{d-1}a_{d-2}\dots a_1a_0\), entonces
$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i}.$$
Los ceros que pasan al principio de la cadena invertida desaparecen naturalmente al interpretar el número. Partiendo de \(x_0=n\), la iteración es
$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$
Denotemos por \(P(x)\iff x=R(x)\) el predicado de palíndromo. Un valor inicial se cuenta exactamente cuando
$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$
Cada valor inicial genera una órbita determinista bajo la transformación \(x\mapsto x+R(x)\). Como la condición de Project Euler sólo pregunta por las primeras 50 imágenes, no hacen falta heurísticas probabilísticas ni conjeturas sobre el comportamiento infinito. El problema se reduce a examinar 9.999 trayectorias independientes dentro del horizonte finito \(t\le 50\).
Formalmente, el conjunto que se cuenta es
$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}.$$
Eso coincide exactamente con las implementaciones: cada número menor que \(10^4\) se prueba por separado, y en cuanto aparece un palíndromo esa trayectoria se elimina del recuento.
La prueba de palíndromo se aplica después de un paso de invertir y sumar, no al dato original. Ese detalle importa. Un número como \(121\) ya es palindrómico, pero la secuencia relevante es
$$121 \to 121+121=242,$$
así que aun así se procesa una iteración y luego tiene éxito de inmediato. La regla de decisión depende de los valores generados \(x_1,x_2,\dots\), no de \(x_0\).
Si \(x\) tiene \(d\) cifras decimales, entonces \(x<10^d\) y también \(R(x)<10^d\). Por lo tanto,
$$x+R(x)<2\cdot 10^d<10^{d+1}.$$
Un solo paso de invertir y sumar puede aumentar el número de cifras a lo sumo en una unidad. Como toda entrada de esta tarea tiene como máximo cuatro cifras, tras 50 pasos cualquier valor intermedio tiene a lo sumo \(4+50=54\) cifras.
Esta cota explica por qué basta una aritmética manual sobre cadenas decimales. Los valores pueden superar los enteros nativos de 64 bits, pero nunca crecen tanto como para poner en apuros una suma con acarreo sobre cadenas.
El ejemplo clásico no Lychrel del enunciado es
$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$
En el tercer valor generado aparece un palíndromo, así que 349 queda fuera de \(\mathcal{L}_{50}\).
Un caso de control aún más simple es \(47\):
$$47 \to 47+74=121.$$
Se vuelve palindrómico de inmediato. En cambio, 196 comienza como
$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$
y no alcanza un palíndromo dentro de las primeras 50 iteraciones. Por eso se cuenta según la regla finita del problema, aunque la versión infinita siga abierta.
Las implementaciones en C++, Python y Java guardan el iterado actual como una cadena decimal. La inversión se obtiene invirtiendo esa cadena, y la suma se realiza cifra por cifra de derecha a izquierda con un acarreo explícito. Es la suma escolar habitual y evita depender de bibliotecas de enteros grandes.
La detección de palíndromos se hace comparando caracteres simétricos desde ambos extremos de la cadena actual. Como todos los valores intermedios permanecen dentro de la cota de 54 cifras, esta representación es simple y suficiente en los tres lenguajes.
Para un solo valor inicial, la implementación repite como mucho 50 veces el mismo bucle: invertir, sumar, comprobar si hay palíndromo y detenerse antes si aparece uno. Un valor inicial sólo se cuenta si las 50 rondas terminan sin éxito.
Después, la rutina exterior aplica esa prueba a cada entero de 1 a 9999 y cuenta los supervivientes. Los parámetros por defecto coinciden con el enunciado de Project Euler, pero el límite superior y el número de iteraciones también pueden cambiarse por línea de comandos. Antes de imprimir el resultado final, los programas verifican ejemplos conocidos como 47 y 349 para confirmar que la regla está implementada correctamente.
Sea \(L=9999\), sea \(S=50\) y sea \(D\) el número máximo de cifras observado durante la ejecución. Cada iteración contiene una inversión, una suma con acarreo y una prueba de palíndromo, todas lineales en la longitud decimal actual. Por tanto, el tiempo total es
$$O(LSD).$$
En el Problema 55, la cota de crecimiento da \(D\le 54\), así que el trabajo total queda en el orden de decenas de millones de operaciones a nivel de carácter. El espacio usado es \(O(D)\), ya que en cada momento el código sólo almacena la cadena decimal actual, su inversión y un pequeño estado de bucle.
对每个满足 \(1 \le n < 10{,}000\) 的整数，反复执行十进制“反转后相加”操作。如果前 50 个新生成的值里没有任何一个是回文数，那么这个起始值在本题中就被计为 Lychrel 数。换句话说，这是一道有限步的计数题，要求统计有多少个起点在规定的 50 步之内始终没有产生回文。
这里的定义是操作性的，而不是绝对数学定义。像 196 这样的起点，在无限制的反转加法过程中仍然属于著名的未决案例。本题并不要求证明它们在无限意义下是否真是 Lychrel 数，只要求把前 50 次迭代精确检查完即可。
记 \(R(x)\) 为 \(x\) 的十进制数字反转。若 \(x\) 的数字写成 \(a_{d-1}a_{d-2}\dots a_1a_0\)，则
$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i}.$$
反转后跑到最前面的零，在数值解释时自然消失。以 \(x_0=n\) 为起点，递推关系是
$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$
把“是回文数”记为谓词 \(P(x)\iff x=R(x)\)。一个起始值恰好在下面条件成立时被计入答案：
$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$
每个起始值在映射 \(x\mapsto x+R(x)\) 下都会生成一条确定性的轨道。由于 Project Euler 的要求只涉及前 50 个后继值，所以根本不需要对无限过程做猜测，也不需要概率性分析。整个问题就是在有限范围 \(t\le 50\) 内检查 9,999 条彼此独立的轨道。
形式化地说，我们统计的集合是
$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}.$$
这与实现完全一致：每个小于 \(10^4\) 的整数单独测试，一旦某一步出现回文，该轨道就立即从计数中剔除。
回文检测发生在一次“反转并相加”之后，而不是直接对原始输入做判断。这一点很关键。比如 \(121\) 本身已经是回文，但题目真正对应的序列是
$$121 \to 121+121=242,$$
也就是说，它仍然要先执行一次迭代，然后才立刻判定成功。判定规则依赖的是生成出来的 \(x_1,x_2,\dots\)，而不是最初的 \(x_0\)。
如果 \(x\) 有 \(d\) 位十进制数字，那么 \(x<10^d\)，同时 \(R(x)<10^d\)。因此
$$x+R(x)<2\cdot 10^d<10^{d+1}.$$
所以一次反转加法最多只会让位数增加 1。由于本题所有输入都不超过四位数，执行 50 步以后，任何中间值的位数都不会超过 \(4+50=54\)。
这正是手写十进制字符串加法足够用的原因。中间值确实可能超出原生 64 位整数范围，但在 50 步限制下远没有大到需要复杂高精度库的程度。
题目中经典的非 Lychrel 例子是
$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$
第三个生成值就已经是回文，因此 349 不属于 \(\mathcal{L}_{50}\)。
更简单的检查样例是 \(47\)：
$$47 \to 47+74=121.$$
它在第一步后就成为回文。相对地，196 的开头几步是
$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$
在前 50 次迭代内都没有出现回文。因此按照本题的有限规则，它会被计入答案，而这与无限过程是否最终出现回文是两回事。
C++、Python 和 Java 三个实现都把当前迭代值保存成十进制字符串。反转操作就是把这个字符串倒过来；加法则从右向左逐位处理，并显式维护进位。这就是普通的竖式加法，因此不依赖任何大整数库。
回文检测通过从字符串两端向中间比较对应字符完成。由于所有中间值都被上面的 54 位上界控制住，这种表示方式在三种语言里都既直接又可靠。
对于某一个起始值，实现最多重复 50 次同样的循环：反转、相加、检测是否为回文；如果中途发现回文，就立刻提前结束。只有在 50 次检查全部失败时，这个起始值才会被计数。
外层过程随后把这一测试应用到 1 到 9999 的每个整数，并统计剩下的候选者。默认参数正好对应 Project Euler 题意，但搜索上界和迭代次数也可以通过命令行修改。在输出最终计数之前，程序还会用 47 和 349 这类熟悉样例做检查，以确认规则被正确实现。
设 \(L=9999\)，\(S=50\)，再设执行过程中出现的最大位数为 \(D\)。每次迭代都包含一次反转、一次带进位的加法和一次回文检测，它们对当前位数都是线性时间。因此总时间复杂度为
$$O(LSD).$$
对第 55 题来说，位数增长上界给出 \(D\le 54\)，所以总工作量只是几千万级别的字符操作。空间复杂度为 \(O(D)\)，因为任意时刻代码只需要保存当前十进制字符串、它的反转结果以及少量循环状态。
Для каждого целого числа \(1 \le n < 10{,}000\) многократно применяется десятичный шаг «перевернуть и сложить». Если среди первых 50 полученных значений не возникает палиндром, исходное число в рамках этой задачи считается числом Лишрела. Значит, нужно просто посчитать, сколько стартовых значений не дают палиндром на всех 50 предписанных шагах.
Ключевая тонкость в том, что это операционное, а не абсолютное определение. Некоторые стартовые значения, например 196, остаются известными открытыми случаями для неограниченного процесса «перевернуть и сложить». Здесь не требуется решать бесконечную версию вопроса; нужно лишь точно проверить первые 50 итераций.
Обозначим через \(R(x)\) десятичное обращение числа \(x\). Если у \(x\) цифры \(a_{d-1}a_{d-2}\dots a_1a_0\), то
$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i}.$$
Нули, которые после обращения оказываются слева, при числовой интерпретации просто исчезают. Начиная с \(x_0=n\), получаем рекурсию
$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$
Предикат палиндрома обозначим через \(P(x)\iff x=R(x)\). Стартовое значение учитывается тогда и только тогда, когда
$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$
Каждое стартовое число порождает детерминированную траекторию под действием преобразования \(x\mapsto x+R(x)\). Поскольку условие Project Euler спрашивает только о первых 50 образах, здесь не нужны ни вероятностные эвристики, ни предположения о бесконечном поведении. Задача сводится к просмотру 9 999 независимых траекторий в конечном горизонте \(t\le 50\).
Формально считается множество
$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}.$$
Именно это делают реализации: каждое число меньше \(10^4\) проверяется отдельно, и как только возникает палиндром, соответствующая траектория исключается из подсчета.
Проверка на палиндром применяется после шага «перевернуть и сложить», а не к исходному вводу. Это важно. Число \(121\) уже является палиндромом, но значимая последовательность такова:
$$121 \to 121+121=242,$$
поэтому оно все равно проходит одну итерацию и затем сразу считается успешным. Правило принятия решения зависит от порожденных значений \(x_1,x_2,\dots\), а не от \(x_0\).
Если число \(x\) имеет \(d\) десятичных цифр, то \(x<10^d\), и также \(R(x)<10^d\). Следовательно,
$$x+R(x)<2\cdot 10^d<10^{d+1}.$$
Значит, один шаг «перевернуть и сложить» может увеличить количество цифр не более чем на единицу. Поскольку все входы в этой задаче имеют не более четырех цифр, после 50 шагов любой промежуточный результат содержит не более \(4+50=54\) цифр.
Эта оценка объясняет, почему полностью хватает ручной десятичной арифметики на строках. Значения могут выйти за пределы 64-битных типов, но при отсечении в 50 шагов они никогда не становятся слишком большими для сложения с переносом.
Классический пример не-Lychrel из условия выглядит так:
$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$
На третьем порожденном значении появляется палиндром, поэтому 349 не принадлежит \(\mathcal{L}_{50}\).
Еще более простой контрольный пример, это \(47\):
$$47 \to 47+74=121.$$
Здесь палиндром возникает сразу. А вот 196 начинается как
$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$
и не достигает палиндрома в пределах первых 50 итераций. Поэтому по конечному правилу задачи 196 включается в счет, независимо от того, что бесконечная версия вопроса остается открытой.
Реализации на C++, Python и Java хранят текущее значение итерации как десятичную строку. Обращение получается простым переворотом этой строки, а сложение выполняется справа налево, цифра за цифрой, с явным переносом. Это обычное школьное сложение, которое позволяет совсем не зависеть от библиотек больших целых чисел.
Проверка на палиндром выполняется симметричным сравнением символов от обоих концов строки. Поскольку все промежуточные значения укладываются в приведенную выше границу в 54 цифры, такое представление остается простым и надежным во всех трех языках.
Для одного стартового значения код повторяет один и тот же цикл не более 50 раз: перевернуть, сложить, проверить на палиндром и досрочно остановиться при первом успехе. Старт учитывается только в том случае, если все 50 раундов заканчиваются без палиндрома.
После этого внешний проход применяет тот же тест ко всем целым числам от 1 до 9999 и считает оставшихся кандидатов. Параметры по умолчанию совпадают с формулировкой Project Euler, но верхнюю границу и число итераций можно менять через командную строку. Перед выводом окончательного количества программы дополнительно проверяют знакомые примеры вроде 47 и 349, чтобы убедиться в корректной реализации правила.
Пусть \(L=9999\), \(S=50\), а \(D\) обозначает максимальное число цифр, встреченное во время выполнения. Каждая итерация содержит одно обращение, одно сложение с переносом и одну проверку на палиндром, то есть три линейных прохода по текущей длине. Поэтому суммарное время работы равно
$$O(LSD).$$
Для задачи 55 оценка роста дает \(D\le 54\), так что общий объем работы составляет лишь десятки миллионов символьных операций. Память равна \(O(D)\), поскольку одновременно хранятся только текущая десятичная строка, ее обращение и небольшой служебный цикл.
لكل عدد صحيح يحقق \(1 \le n < 10{,}000\)، نكرر خطوة قلب الأرقام العشرية ثم الجمع. إذا لم يظهر أي عدد متناظر بين أول 50 قيمة مولدة، فإن قيمة البداية تُعد في هذه المسألة عددًا من أعداد Lychrel. لذلك فالمطلوب هو مسألة عد منتهية: كم قيمة ابتدائية تبقى غير متناظرة طوال الخطوات الخمسين المطلوبة.
النقطة المهمة أن هذا تعريف إجرائي لا تعريف مطلق. بعض القيم الابتدائية مثل 196 هي حالات مشهورة غير محسومة في العملية غير المحدودة لقلب الأرقام والجمع. في هذه المسألة لا نحتاج إلى حسم ما إذا كانت Lychrel حقًا على المدى اللانهائي، بل يكفي أن نفحص أول 50 تكرارًا بدقة.
لنرمز بـ \(R(x)\) إلى قلب التمثيل العشري للعدد \(x\). إذا كانت أرقام \(x\) هي \(a_{d-1}a_{d-2}\dots a_1a_0\)، فإن
$$R(x)=\sum_{i=0}^{d-1} a_i 10^{d-1-i}.$$
الأصفار التي تنتقل إلى مقدمة السلسلة بعد القلب تختفي طبيعيًا عند تفسير القيمة عددًا صحيحًا. إذا بدأنا من \(x_0=n\)، فإن التكرار يصبح
$$x_{t+1}=x_t+R(x_t)\qquad (t\ge 0).$$
ولنكتب خاصية التناظر على صورة \(P(x)\iff x=R(x)\). تُحسب قيمة البداية بالضبط عندما يتحقق الشرط
$$\forall t\in\{1,2,\dots,50\},\ \neg P(x_t).$$
كل قيمة ابتدائية تولد مسارًا حتميًا تحت التحويل \(x\mapsto x+R(x)\). وبما أن شرط Project Euler يسأل فقط عن أول 50 صورة، فلا حاجة إلى تخمينات احتمالية ولا إلى نظريات عن السلوك اللانهائي. تختزل المسألة إلى فحص 9999 مسارًا مستقلًا داخل الأفق المنتهي \(t\le 50\).
بصورة رسمية، المجموعة التي نعدها هي
$$\mathcal{L}_{50}=\{\,n\in\{1,2,\dots,9999\}:\forall t\in\{1,2,\dots,50\},\ \neg P(x_t(n))\,\}.$$
وهذا يطابق التنفيذ حرفيًا: كل عدد أصغر من \(10^4\) يُختبر وحده، وبمجرد ظهور متناظر تُزال تلك السلسلة من العد.
اختبار التناظر لا يُطبَّق على الإدخال الأصلي، بل بعد خطوة قلب وجمع واحدة. هذه تفصيلة مهمة. فالعدد \(121\) متناظر أصلًا، لكن السلسلة ذات الصلة هي
$$121 \to 121+121=242,$$
ولذلك ما زال يمر عبر خطوة واحدة ثم ينجح فورًا. قاعدة القرار تعتمد على القيم المولدة \(x_1,x_2,\dots\)، لا على \(x_0\) نفسه.
إذا كان \(x\) مكوّنًا من \(d\) أرقام عشرية، فلدينا \(x<10^d\) وكذلك \(R(x)<10^d\). ومن ثم
$$x+R(x)<2\cdot 10^d<10^{d+1}.$$
إذن خطوة قلب وجمع واحدة لا يمكن أن تزيد عدد الأرقام بأكثر من واحد. وبما أن كل إدخال في هذه المسألة لا يتجاوز أربع خانات، فإن أي قيمة وسطية بعد 50 خطوة تبقى ضمن \(4+50=54\) خانة على الأكثر.
هذا الحد يفسر لماذا تكفي تمامًا الحسابات اليدوية على السلاسل العشرية. قد تتجاوز القيم حدود الأعداد الصحيحة الأصلية ذات 64 بت، لكنها لا تصبح ضخمة إلى درجة تتطلب مكتبات عددية خاصة ضمن حد 50 خطوة.
المثال الكلاسيكي غير المنتمي إلى Lychrel في نص المسألة هو
$$349 \to 349+943=1292 \to 1292+2921=4213 \to 4213+3124=7337.$$
يظهر عدد متناظر عند القيمة الثالثة المولدة، لذلك لا ينتمي 349 إلى \(\mathcal{L}_{50}\).
وهناك مثال تحقق أبسط هو \(47\):
$$47 \to 47+74=121.$$
فيصبح متناظرًا مباشرة. أما 196 فيبدأ على الصورة
$$196 \to 887 \to 1675 \to 7436 \to 13783 \to \cdots$$
ولا يصل إلى متناظر خلال أول 50 تكرارًا. لذلك يُحسب وفق القاعدة المنتهية للمسألة، بصرف النظر عن كون النسخة اللانهائية من السؤال ما زالت مفتوحة.
تحتفظ تطبيقات C++ وPython وJava بالقيمة الحالية على شكل سلسلة عشرية. يتم الحصول على المعكوس بقلب هذه السلسلة، ثم تنفَّذ عملية الجمع خانة بخانة من اليمين إلى اليسار مع حمل صريح. هذه هي طريقة الجمع المدرسية المعتادة، وهي تزيل الحاجة إلى أي مكتبات للأعداد الصحيحة الكبيرة.
أما اختبار التناظر فيتم بمقارنة المحارف المتماثلة من طرفي السلسلة الحالية. وبما أن كل القيم الوسيطة تبقى ضمن حد 54 خانة المذكور أعلاه، فإن هذا التمثيل بسيط وموثوق وكافٍ تمامًا في اللغات الثلاث.
بالنسبة إلى قيمة ابتدائية واحدة، يكرر التنفيذ الحلقة نفسها 50 مرة كحد أقصى: قلب، جمع، اختبار تناظر، ثم توقف مبكر إذا ظهر متناظر. ولا تُحسب قيمة البداية إلا إذا فشلت الجولات الخمسون كلها في إنتاج متناظر.
بعد ذلك تطبّق الحلقة الخارجية الاختبار نفسه على كل عدد من 1 إلى 9999 وتعدّ القيم الباقية. المعلمات الافتراضية تطابق نص Project Euler، لكن حد البحث وعدد التكرارات يمكن تعديلهما أيضًا من سطر الأوامر. وقبل طباعة الناتج النهائي تتحقق البرامج من أمثلة معروفة مثل 47 و349 للتأكد من أن القاعدة نُفذت بصورة صحيحة.
لنأخذ \(L=9999\) و\(S=50\)، ولتكن \(D\) أكبر قيمة لعدد الخانات تظهر أثناء التنفيذ. كل تكرار يتضمن عملية قلب واحدة، وعملية جمع مع حمل واحدة، واختبار تناظر واحدًا، وجميعها خطية في طول السلسلة الحالية. لذلك يكون زمن التنفيذ الكلي
$$O(LSD).$$
في المسألة 55 يعطي حد النمو \(D\le 54\)، ولذلك يبقى إجمالي العمل في حدود عشرات الملايين من العمليات على مستوى المحارف. واستهلاك الذاكرة هو \(O(D)\)، لأن الكود لا يحتفظ في أي لحظة إلا بالسلسلة العشرية الحالية، ومعكوسها، ومقدار صغير من حالة الحلقة.