A positive integer \(n\) is called reversible when \(n+\operatorname{rev}(n)\) is made entirely of odd digits, and neither \(n\) nor its reversal is allowed to acquire leading zeros. For numbers below \(10^9\), that means counting all valid lengths from 1 through 9 while excluding any number ending in 0.
The important point is that reversibility is controlled by base-10 addition with carries. Once the digits are grouped into mirrored pairs, the search stops being about individual integers and becomes a finite combinatorial count over pair sums and carry states.
Write an \(L\)-digit number as
$$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0.$$
The condition \(x_0\neq 0\) is exactly the rule that the reversal may not begin with 0. The whole argument comes from studying the addition \(n+\operatorname{rev}(n)\) column by column.
Column \(i\) adds the mirrored digits \(x_i\) and \(x_{L-1-i}\). With incoming carry \(c_i\) and \(c_0=0\), define
$$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor.$$
Reversibility means every visible digit \(d_i\) is odd. Because \(x_i+x_{L-1-i}\le 18\), every carry is either 0 or 1. If a final carry remains after the most significant column, it can only be 1, and that extra leading digit is still odd, so it is harmless.
This immediately gives the parity rule used by the implementations: if the incoming carry is 0, then the mirrored digit sum must be odd; if the incoming carry is 1, then the mirrored digit sum must be even.
Let \(h=\lfloor L/2\rfloor\) and define the mirrored pair sums
$$s_j=x_j+x_{L-1-j}\qquad (0\le j \lt h).$$
The exact ordered pair of digits matters only through its sum and through how many digit pairs realize that sum. For the outermost pair both digits must be nonzero, so
$$O(s)=\#\{(a,b)\in\{1,\dots,9\}^2:a+b=s\}.$$
For inner pairs zeros are allowed, so
$$I(s)=\#\{(a,b)\in\{0,\dots,9\}^2:a+b=s\}.$$
These multiplicities are
$$O(s)=\begin{cases} s-1,&2\le s\le 10,\\ 19-s,&11\le s\le 18,\\ 0,&\text{otherwise,} \end{cases} \qquad I(s)=\begin{cases} s+1,&0\le s\le 9,\\ 19-s,&10\le s\le 18,\\ 0,&\text{otherwise.} \end{cases}$$
So a chosen sum pattern \((s_0,\dots,s_{h-1})\) carries weight \(O(s_0)\prod_{j=1}^{h-1} I(s_j)\). If \(L\) is odd, we also choose a middle digit \(m\), whose column contributes \(2m\).
For even \(L\), the column-sum sequence is
$$s_0,s_1,\dots,s_{h-1},s_{h-1},\dots,s_1,s_0.$$
For odd \(L\), it becomes
$$s_0,s_1,\dots,s_{h-1},2m,s_{h-1},\dots,s_1,s_0.$$
The same pair sum \(s_j\) appears twice. Therefore the carry entering its first appearance and the carry entering its mirrored appearance must be equal; otherwise one occurrence would require \(s_j\) to be odd and the other would require it to be even. Matching the first half with the mirrored second half yields the recurrence
$$c_{j+1}=c_{j-1}\qquad (1\le j \lt h).$$
So the carry pattern on the way toward the middle has period 2. That is the key invariant behind both the formulas and the code.
Let \(L=2k\). The central mirrored pair is used in two consecutive columns, so its two incoming carries must agree. Together with \(c_{j+1}=c_{j-1}\) and \(c_0=0\), this forces
$$c_0=c_1=\cdots=c_k=0.$$
Hence every mirrored sum must be odd and strictly below 10. A larger odd sum would create a carry and immediately break the all-zero pattern. The outer pair then has 20 choices, coming from odd sums \(3,5,7,9\) with multiplicities \(2,4,6,8\). Each inner pair has 30 choices, coming from odd sums \(1,3,5,7,9\) with multiplicities \(2,4,6,8,10\).
Therefore the number of reversible numbers with \(2k\) digits is
$$R_{2k}=20\cdot 30^{k-1}.$$
For the present range this gives
$$R_2=20,\qquad R_4=600,\qquad R_6=18000,\qquad R_8=540000.$$
Let \(L=2k+1\). The middle column is \(2m+c_k\). Since \(2m\) is even and the resulting digit must be odd, we must have
$$c_k=1.$$
But the recurrence \(c_{j+1}=c_{j-1}\) with \(c_0=0\) makes the carries alternate:
$$0,1,0,1,\dots.$$
So \(c_k=1\) is possible only when \(k\) is odd, which means \(L\equiv 3 \pmod 4\). This proves that lengths \(1,5,9,\dots\) contribute nothing.
When \(L=4m+3\), the alternating pattern fixes the allowed sum types. The outer pair must move from carry 0 to carry 1, so its sum must be odd and at least 11, giving 20 choices. Each inner step from carry 1 to carry 0 needs an even sum below 10, giving 25 choices. Each inner step from carry 0 to carry 1 needs an odd sum above 10, giving 20 choices. The middle digit must satisfy \(2m+1 \lt 10\), so there are 5 choices.
Thus
$$R_{4m+3}=20\cdot(25\cdot 20)^m\cdot 5=100\cdot 500^m,\qquad R_{4m+1}=0.$$
Below \(10^9\) this yields
$$R_3=100,\qquad R_7=50000,\qquad R_5=R_9=0.$$
The 2-digit number \(36\) is reversible because \(36+63=99\). The only mirrored sum is \(3+6=9\), which is odd and below 10, so neither column creates a carry.
The 3-digit number \(219\) is reversible because \(219+912=1131\). The outer sum is \(2+9=11\), so the carry pattern begins \(0\to 1\). The middle column is \(2\cdot 1+1=3\), which returns the carry to 0. The last outer column again contributes 11 and produces the leading 1. Every digit of \(1131\) is odd, exactly as the carry analysis predicts.
Adding the nonzero counts gives the total below \(10^9\):
$$20+100+600+18000+50000+540000=608720.$$
The C++, Python, and Java implementations do not brute-force all integers below one billion. Instead, they build the combinatorial count directly from mirrored digit-pair sums.
The implementation first counts how many ordered digit pairs produce each sum from 0 to 18. One table is for the outer pair, where both digits must lie in \(\{1,\dots,9\}\). The other is for inner pairs, where digits may be 0. This turns many different digit assignments into a single weighted state.
For each digit length from 2 through 9, the implementation chooses the sequence \((s_0,\dots,s_{h-1})\) recursively. Every time a new mirrored sum is chosen, the running weight is multiplied by the number of digit pairs that realize it. For odd lengths, the implementation also tries all 10 possible middle digits.
Once a full sum pattern has been chosen, the implementation reconstructs the column sequence \(s_0,\dots,s_{h-1},2m,s_{h-1},\dots,s_0\) when needed, then simulates the addition from right to left. If any produced digit is even, the pattern is discarded immediately. Otherwise its accumulated weight is added to the answer. The C++ version also includes small checkpoint counts such as \(R_2=20\), \(R_3=100\), and \(R_7=50000\) as sanity checks.
The code is a direct implementation of the mathematics above: mirrored digit pairs are collapsed into sum states, the carry recurrence is evaluated exactly, and multiplicities account for all concrete digit choices. The closed forms \(20\cdot 30^{k-1}\) and \(100\cdot 500^m\) are consequences of those rules, not separate assumptions.
For a fixed length \(L\), the search explores at most \(19^{\lfloor L/2\rfloor}\) mirrored-sum patterns, with an extra factor of 10 for odd lengths because of the middle digit. Each completed pattern is checked in \(O(L)\) time by simulating the carries. So the generic complexity per length is
$$O\!\left(L\cdot 19^{\lfloor L/2\rfloor}\right),$$
with \(O(L)\) memory for the current pattern and carry scan.
For this problem \(L\le 9\), so the actual runtime is tiny. Mathematically, once the carry invariants are recognized, the answer can even be written in closed form; the implementations keep the weighted DFS because it is short, exact, and still effectively constant-time for the required range.
Eine positive ganze Zahl \(n\) heißt reversibel, wenn \(n+\operatorname{rev}(n)\) nur aus ungeraden Ziffern besteht und weder \(n\) noch seine Umkehrung führende Nullen besitzen dürfen. Unterhalb von \(10^9\) müssen also alle Längen von 1 bis 9 betrachtet werden, wobei Zahlen mit Endziffer 0 automatisch ausgeschlossen sind.
Entscheidend ist, dass diese Eigenschaft vollständig durch die Überträge der schriftlichen Addition bestimmt wird. Sobald man die Ziffern zu gespiegelten Paaren zusammenfasst, wird aus einer Suche über Milliarden Zahlen ein endliches kombinatorisches Zählproblem über Paarsummen und Carry-Zustände.
Schreibe eine \(L\)-stellige Zahl als
$$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0.$$
Die Bedingung \(x_0\neq 0\) ist genau das Verbot, dass die umgedrehte Zahl mit 0 beginnt. Die gesamte Herleitung entsteht aus der spaltenweisen Untersuchung von \(n+\operatorname{rev}(n)\).
In Spalte \(i\) werden die gespiegelten Ziffern \(x_i\) und \(x_{L-1-i}\) addiert. Mit eingehendem Übertrag \(c_i\) und \(c_0=0\) setzen wir
$$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor.$$
Reversibilität bedeutet, dass jede sichtbare Ziffer \(d_i\) ungerade ist. Da stets \(x_i+x_{L-1-i}\le 18\) gilt, kann jeder Übertrag nur 0 oder 1 sein. Falls nach der höchsten Spalte noch ein Übertrag übrig bleibt, ist er notwendigerweise 1 und damit selbst wieder ungerade.
Damit erhält man sofort die Paritätsregel, die auch in den Implementierungen steckt: bei eingehendem Übertrag 0 muss die gespiegelte Ziffernsumme ungerade sein; bei eingehendem Übertrag 1 muss sie gerade sein.
Sei \(h=\lfloor L/2\rfloor\) und definiere die gespiegelten Paarsummen
$$s_j=x_j+x_{L-1-j}\qquad (0\le j \lt h).$$
Für das Zählen ist nicht das geordnete Ziffernpaar selbst entscheidend, sondern nur seine Summe und die Anzahl der Paare mit genau dieser Summe. Für das äußere Paar müssen beide Ziffern ungleich 0 sein, also
$$O(s)=\#\{(a,b)\in\{1,\dots,9\}^2:a+b=s\}.$$
Bei inneren Paaren sind Nullen erlaubt, also
$$I(s)=\#\{(a,b)\in\{0,\dots,9\}^2:a+b=s\}.$$
Explizit gilt
$$O(s)=\begin{cases} s-1,&2\le s\le 10,\\ 19-s,&11\le s\le 18,\\ 0,&\text{sonst,} \end{cases} \qquad I(s)=\begin{cases} s+1,&0\le s\le 9,\\ 19-s,&10\le s\le 18,\\ 0,&\text{sonst.} \end{cases}$$
Ein gewähltes Summenmuster \((s_0,\dots,s_{h-1})\) besitzt also das Gewicht \(O(s_0)\prod_{j=1}^{h-1} I(s_j)\). Bei ungerader Länge kommt zusätzlich eine mittlere Ziffer \(m\) hinzu, deren Spalte den Wert \(2m\) liefert.
Bei geradem \(L\) lautet die Folge der Spaltensummen
$$s_0,s_1,\dots,s_{h-1},s_{h-1},\dots,s_1,s_0,$$
bei ungeradem \(L\) dagegen
$$s_0,s_1,\dots,s_{h-1},2m,s_{h-1},\dots,s_1,s_0.$$
Dieselbe Summe \(s_j\) tritt also zweimal auf. Deshalb muss der Übertrag, der in ihr erstes Auftreten hineinläuft, gleich dem Übertrag des gespiegelten Auftretens sein; sonst müsste dieselbe Summe einmal ungerade und einmal gerade sein. Durch den Abgleich der ersten Hälfte mit der gespiegelten zweiten Hälfte erhält man
$$c_{j+1}=c_{j-1}\qquad (1\le j \lt h).$$
Das Übertragsmuster auf dem Weg zur Mitte ist also periodisch mit Periode 2. Genau dieses Invarianzargument trägt die ganze Lösung.
Sei \(L=2k\). Das zentrale gespiegelte Paar wird in zwei aufeinanderfolgenden Spalten benutzt, daher müssen seine beiden eingehenden Überträge übereinstimmen. Zusammen mit \(c_{j+1}=c_{j-1}\) und \(c_0=0\) folgt
$$c_0=c_1=\cdots=c_k=0.$$
Damit muss jede gespiegelte Summe ungerade und strikt kleiner als 10 sein. Eine größere ungerade Summe würde sofort einen Übertrag erzeugen und das Nullmuster zerstören. Für das äußere Paar gibt es 20 Möglichkeiten: die ungeraden Summen \(3,5,7,9\) mit Vielfachheiten \(2,4,6,8\). Jedes innere Paar besitzt 30 Möglichkeiten: die ungeraden Summen \(1,3,5,7,9\) mit Vielfachheiten \(2,4,6,8,10\).
Daher ist die Anzahl reversibler Zahlen mit \(2k\) Stellen gleich
$$R_{2k}=20\cdot 30^{k-1}.$$
Im vorliegenden Bereich ergibt das
$$R_2=20,\qquad R_4=600,\qquad R_6=18000,\qquad R_8=540000.$$
Sei \(L=2k+1\). Die mittlere Spalte ist \(2m+c_k\). Da \(2m\) gerade ist und die entstehende Ziffer ungerade sein muss, gilt notwendig
$$c_k=1.$$
Die Rekurrenz \(c_{j+1}=c_{j-1}\) zusammen mit \(c_0=0\) erzwingt jedoch das alternierende Muster
$$0,1,0,1,\dots.$$
Also kann \(c_k=1\) nur dann eintreten, wenn \(k\) ungerade ist, also genau dann, wenn \(L\equiv 3 \pmod 4\). Damit ist sofort klar, dass Längen \(1,5,9,\dots\) nichts beitragen.
Für \(L=4m+3\) legt dieses Alternieren alle zulässigen Summenarten fest. Das äußere Paar muss von Carry 0 nach Carry 1 wechseln, seine Summe muss also ungerade und mindestens 11 sein, was 20 Möglichkeiten liefert. Jeder innere Schritt von Carry 1 nach Carry 0 benötigt eine gerade Summe unter 10 und liefert 25 Möglichkeiten. Jeder innere Schritt von Carry 0 nach Carry 1 benötigt eine ungerade Summe über 10 und liefert 20 Möglichkeiten. Die mittlere Ziffer muss \(2m+1 \lt 10\) erfüllen, also gibt es 5 Möglichkeiten.
Somit gilt
$$R_{4m+3}=20\cdot(25\cdot 20)^m\cdot 5=100\cdot 500^m,\qquad R_{4m+1}=0.$$
Unterhalb von \(10^9\) folgt daraus
$$R_3=100,\qquad R_7=50000,\qquad R_5=R_9=0.$$
Die 2-stellige Zahl \(36\) ist reversibel, denn \(36+63=99\). Die einzige gespiegelte Summe ist \(3+6=9\); sie ist ungerade und kleiner als 10, also entsteht in keiner Spalte ein Übertrag.
Die 3-stellige Zahl \(219\) ist reversibel, denn \(219+912=1131\). Die äußere Summe ist \(2+9=11\), daher beginnt das Carry-Muster mit \(0\to 1\). Die mittlere Spalte ist \(2\cdot 1+1=3\) und setzt den Übertrag wieder auf 0 zurück. Die letzte äußere Spalte liefert erneut 11 und erzeugt die führende 1. Genau wie vorhergesagt sind alle Ziffern von \(1131\) ungerade.
Die Summe der nichtverschwindenden Beiträge unterhalb von \(10^9\) ist
$$20+100+600+18000+50000+540000=608720.$$
Die C++-, Python- und Java-Implementierungen testen nicht jede Zahl unter einer Milliarde einzeln. Stattdessen berechnen sie direkt die kombinatorische Anzahl aus den gespiegelten Ziffernsummen.
Zuerst wird für jede Summe von 0 bis 18 gezählt, wie viele geordnete Ziffernpaare sie erzeugen. Eine Tabelle gilt für das äußere Paar mit Ziffern aus \(\{1,\dots,9\}\), die andere für innere Paare mit Ziffern aus \(\{0,\dots,9\}\). Dadurch werden viele konkrete Zahlen zu einem einzigen gewichteten Zustand zusammengefasst.
Für jede Stellenzahl von 2 bis 9 wählt die Implementierung rekursiv die Folge \((s_0,\dots,s_{h-1})\). Jedes Mal, wenn eine weitere gespiegelte Summe gewählt wird, wird das laufende Gewicht mit der Anzahl der dazugehörigen Ziffernpaare multipliziert. Bei ungeraden Längen werden zusätzlich alle 10 mittleren Ziffern ausprobiert.
Sobald ein komplettes Summenmuster vorliegt, baut die Implementierung die Spaltenfolge \(s_0,\dots,s_{h-1},2m,s_{h-1},\dots,s_0\) auf und simuliert die Addition von rechts nach links. Erzeugt irgendeine Spalte eine gerade Ziffer, wird das Muster sofort verworfen. Andernfalls wird sein Gewicht zum Ergebnis addiert. Die C++-Version enthält zusätzlich kleine Kontrollwerte wie \(R_2=20\), \(R_3=100\) und \(R_7=50000\) als Plausibilitätsprüfung.
Der Code setzt die Mathematik direkt um: gespiegelte Ziffernpaare werden auf Summenzustände reduziert, die Carry-Rekurrenz wird exakt ausgewertet, und die Vielfachheiten zählen alle konkreten Ziffernbelegungen mit. Die geschlossenen Formeln \(20\cdot 30^{k-1}\) und \(100\cdot 500^m\) sind Konsequenzen dieser Regeln, keine separaten Annahmen.
Für eine feste Länge \(L\) werden höchstens \(19^{\lfloor L/2\rfloor}\) Muster gespiegelter Summen betrachtet; bei ungeraden Längen kommt wegen der mittleren Ziffer noch ein Faktor 10 hinzu. Jedes vollständige Muster wird in \(O(L)\) Zeit durch eine Carry-Simulation geprüft. Die generische Laufzeit pro Länge ist also
$$O\!\left(L\cdot 19^{\lfloor L/2\rfloor}\right),$$
bei \(O(L)\) Speicher für das aktuelle Muster und die Übertragsprüfung.
Hier gilt jedoch \(L\le 9\), also ist die reale Laufzeit winzig. Sobald die Carry-Invarianten erkannt sind, kann man die Antwort sogar direkt in geschlossener Form hinschreiben; die Implementierungen behalten dennoch die gewichtete Tiefensuche bei, weil sie kurz, exakt und für den geforderten Bereich praktisch konstant schnell ist.
Pozitif bir tam sayı \(n\), \(n+\operatorname{rev}(n)\) toplamının tüm basamakları tek olduğunda reversible kabul edilir; ayrıca ne \(n\) ne de ters çevrilmiş hali başta sıfır içeremez. \(10^9\)'un altındaki sayılar için bu, 1 ile 9 basamak arasındaki tüm uzunlukları saymak ve sonu 0 ile biten sayıları otomatik olarak dışlamak anlamına gelir.
Belirleyici nokta şudur: bu özellik tamamen onluk sistemdeki toplama elde zinciriyle kontrol edilir. Basamaklar simetrik çiftler halinde gruplanınca, milyarlarca sayıyı tek tek denemek yerine çift toplamları ve elde durumları üzerinde sonlu bir kombinatorik sayım yapmak yeterli olur.
\(L\) basamaklı bir sayıyı
$$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0$$
şeklinde yazalım. Buradaki \(x_0\neq 0\) koşulu, ters çevrilen sayının başında 0 olamayacağı anlamına gelir. Tüm çözüm, \(n+\operatorname{rev}(n)\) toplamını sütun sütun incelemekten doğar.
\(i\). sütunda \(x_i\) ile \(x_{L-1-i}\) toplanır. Giriş eldesi \(c_i\) ve \(c_0=0\) olmak üzere
$$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor$$
tanımlarını yapalım. Reversible olma şartı, görünen her \(d_i\) basamağının tek olmasıdır. Çünkü \(x_i+x_{L-1-i}\le 18\), bütün eldeler yalnızca 0 veya 1 olabilir. En solda fazladan bir elde kalırsa bu da ancak 1 olabilir ve o yeni öndeki basamak da zaten tektir.
Böylece uygulamaların kullandığı temel parite kuralı ortaya çıkar: giriş eldesi 0 ise simetrik basamak toplamı tek olmalıdır; giriş eldesi 1 ise bu toplam çift olmalıdır.
\(h=\lfloor L/2\rfloor\) olsun ve simetrik çift toplamlarını
$$s_j=x_j+x_{L-1-j}\qquad (0\le j \lt h)$$
şeklinde tanımlayalım. Gerçekte önemli olan, sıralı basamak çiftinin kendisi değil, bu toplam ve bu toplamı üreten kaç farklı basamak çifti olduğudur. Dıştaki çiftte her iki basamak da sıfırdan farklı olmalıdır:
$$O(s)=\#\{(a,b)\in\{1,\dots,9\}^2:a+b=s\}.$$
İç çiftlerde ise sıfıra izin vardır:
$$I(s)=\#\{(a,b)\in\{0,\dots,9\}^2:a+b=s\}.$$
Açık biçimde
$$O(s)=\begin{cases} s-1,&2\le s\le 10,\\ 19-s,&11\le s\le 18,\\ 0,&\text{aksi halde,} \end{cases} \qquad I(s)=\begin{cases} s+1,&0\le s\le 9,\\ 19-s,&10\le s\le 18,\\ 0,&\text{aksi halde.} \end{cases}$$
Dolayısıyla seçilmiş bir \((s_0,\dots,s_{h-1})\) örüntüsünün ağırlığı \(O(s_0)\prod_{j=1}^{h-1} I(s_j)\) olur. Eğer \(L\) tek ise, orta basamak için ayrıca bir \(m\) seçilir ve orta sütun \(2m\) katkısı yapar.
\(L\) çift ise sütun toplamları sırası
$$s_0,s_1,\dots,s_{h-1},s_{h-1},\dots,s_1,s_0$$
olur. \(L\) tek ise sıra
$$s_0,s_1,\dots,s_{h-1},2m,s_{h-1},\dots,s_1,s_0$$
şeklindedir. Aynı \(s_j\) değeri iki kez kullanıldığı için, bu iki kullanıma giren eldenin de aynı olması gerekir; aksi halde aynı toplam bir yerde tek, başka bir yerde çift olmak zorunda kalır. İlk yarı ile simetrik ikinci yarıyı karşılaştırınca
$$c_{j+1}=c_{j-1}\qquad (1\le j \lt h)$$
bağıntısı elde edilir. Yani merkeze doğru giderken elde örüntüsü 2 periyotlu olur. Çözümün asıl değişmezi budur.
\(L=2k\) olsun. Merkeze en yakın simetrik çift arka arkaya iki sütunda kullanılır; bu yüzden bu iki sütuna giren eldeler eşit olmalıdır. Bunu \(c_{j+1}=c_{j-1}\) ve \(c_0=0\) ile birleştirince
$$c_0=c_1=\cdots=c_k=0$$
zorunlu olur. O halde her simetrik toplam tek ve 10'dan küçük olmalıdır. Daha büyük bir tek toplam anında elde üretir ve tüm sıfır örüntüsünü bozar. Dış çift için 20 seçim vardır: çoklukları \(2,4,6,8\) olan \(3,5,7,9\) tek toplamları. Her iç çift için ise çoklukları \(2,4,6,8,10\) olan \(1,3,5,7,9\) toplamlarından toplam 30 seçim vardır.
Buna göre \(2k\) basamaklı reversible sayıların sayısı
$$R_{2k}=20\cdot 30^{k-1}$$
olur. Bu problemde
$$R_2=20,\qquad R_4=600,\qquad R_6=18000,\qquad R_8=540000$$
elde edilir.
\(L=2k+1\) olsun. Orta sütun \(2m+c_k\) biçimindedir. \(2m\) çift olduğu için, ortaya çıkan basamağın tek olması ancak
$$c_k=1$$
ile mümkündür. Fakat \(c_{j+1}=c_{j-1}\) bağıntısı ve \(c_0=0\), eldeleri
$$0,1,0,1,\dots$$
şeklinde dönüşümlü hale getirir. Bu yüzden \(c_k=1\) ancak \(k\) tek ise mümkündür; yani ancak \(L\equiv 3 \pmod 4\) uzunlukları çalışır. Böylece \(1,5,9,\dots\) basamaklı sayılar doğrudan sıfır katkı verir.
\(L=4m+3\) olduğunda bu dönüşümlü örüntü her toplam türünü belirler. Dış çift, eldeyi 0'dan 1'e taşımalıdır; dolayısıyla toplamı tek ve en az 11 olmalıdır, bu da 20 seçim verir. Elde 1'den 0'a inen her iç adım için 10'dan küçük çift toplam gerekir, yani 25 seçim. Elde 0'dan 1'e çıkan her iç adım için 10'dan büyük tek toplam gerekir, yani 20 seçim. Orta basamak ayrıca \(2m+1 \lt 10\) koşulunu sağlamalıdır; bu da 5 seçim demektir.
Sonuç olarak
$$R_{4m+3}=20\cdot(25\cdot 20)^m\cdot 5=100\cdot 500^m,\qquad R_{4m+1}=0$$
olur. \(10^9\)'un altında bu
$$R_3=100,\qquad R_7=50000,\qquad R_5=R_9=0$$
değerlerini verir.
İki basamaklı \(36\) sayısı reversible'dır, çünkü \(36+63=99\). Tek simetrik toplam \(3+6=9\)'dur; hem tektir hem de 10'dan küçüktür, bu yüzden hiçbir sütunda elde oluşmaz.
Üç basamaklı \(219\) sayısı da reversible'dır, çünkü \(219+912=1131\). Dış toplam \(2+9=11\) olduğundan elde örüntüsü \(0\to 1\) ile başlar. Orta sütun \(2\cdot 1+1=3\) üretir ve eldeyi tekrar 0'a indirir. Son dış sütun yine 11 verir ve baştaki 1'i üretir. Böylece \(1131\)'in bütün basamakları tek olur.
Sıfırdan farklı katkıları topladığımızda \(10^9\)'un altındaki toplam sayı
$$20+100+600+18000+50000+540000=608720$$
çıkar.
C++, Python ve Java uygulamaları bir milyarın altındaki tüm sayıları tek tek denemez. Bunun yerine, simetrik basamak çifti toplamlarından doğrudan kombinatorik sayımı kurar.
Önce 0 ile 18 arasındaki her toplam için, o toplamı üreten sıralı basamak çifti sayısı hesaplanır. Bir tablo dış çift içindir ve basamaklar \(\{1,\dots,9\}\) kümesinden gelir. Diğer tablo iç çiftler içindir ve \(\{0,\dots,9\}\) kullanılır. Böylece çok sayıda somut sayı tek bir ağırlıklı duruma indirgenir.
Her uzunluk için 2'den 9'a kadar \((s_0,\dots,s_{h-1})\) dizisi özyinelemeli olarak seçilir. Her yeni toplam seçildiğinde geçerli düzen sayısı ilgili çokluk kadar çarpılır. Tek uzunluklarda orta basamak için de 10 olasılık ayrı ayrı denenir.
Bir örüntü tamamlandığında uygulama gerekirse \(s_0,\dots,s_{h-1},2m,s_{h-1},\dots,s_0\) sütun dizisini kurar ve toplamayı sağdan sola simüle eder. Üretilen basamaklardan biri çift çıkarsa bu örüntü hemen elenir. Aksi halde birikmiş ağırlığı cevaba eklenir. C++ sürümü ayrıca \(R_2=20\), \(R_3=100\) ve \(R_7=50000\) gibi küçük kontrol değerleriyle yöntemi doğrular.
Kod, yukarıdaki matematiği doğrudan uygular: simetrik basamak çiftleri toplam durumlarına indirgenir, elde bağıntısı eksiksiz değerlendirilir ve çokluklar tüm gerçek basamak seçimlerini hesaba katar. \(20\cdot 30^{k-1}\) ve \(100\cdot 500^m\) kapalı formları bağımsız varsayımlar değil, tam olarak bu kuralların sonucudur.
Sabit bir \(L\) uzunluğu için en fazla \(19^{\lfloor L/2\rfloor}\) kadar simetrik toplam örüntüsü dolaşılır; tek uzunluklarda orta basamak nedeniyle buna ek bir 10 çarpanı gelir. Her tamamlanmış örüntü, elde simülasyonu ile \(O(L)\) zamanda kontrol edilir. Dolayısıyla genel karmaşıklık
$$O\!\left(L\cdot 19^{\lfloor L/2\rfloor}\right)$$
ve bellek kullanımı da mevcut örüntü ile elde taraması için \(O(L)\)'dir.
Burada \(L\le 9\) olduğundan gerçek çalışma süresi çok küçüktür. Matematiksel değişmezler görüldüğünde cevap kapalı formda da yazılabilir; yine de uygulamalar, kısa, kesin ve bu aralık için fiilen sabit zamanlı olduğu için ağırlıklı DFS yaklaşımını korur.
Un entero positivo \(n\) es reversible cuando \(n+\operatorname{rev}(n)\) está formado solo por dígitos impares, y además ni \(n\) ni su inversión pueden adquirir ceros iniciales. Debajo de \(10^9\), eso obliga a contar todas las longitudes entre 1 y 9 y a excluir de entrada los números terminados en 0.
La idea central es que la propiedad depende por completo de los acarreos de la suma en base 10. Una vez que los dígitos se agrupan en pares reflejados, el problema deja de ser una búsqueda sobre miles de millones de enteros y pasa a ser un conteo combinatorio finito sobre sumas de pares y estados de acarreo.
Escribamos un número de \(L\) cifras como
$$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0.$$
La condición \(x_0\neq 0\) expresa exactamente que la inversión no puede empezar con 0. Toda la derivación sale de estudiar \(n+\operatorname{rev}(n)\) columna por columna.
La columna \(i\) suma los dígitos reflejados \(x_i\) y \(x_{L-1-i}\). Con acarreo entrante \(c_i\) y \(c_0=0\), definimos
$$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor.$$
Ser reversible significa que cada dígito visible \(d_i\) es impar. Como siempre se cumple \(x_i+x_{L-1-i}\le 18\), cada acarreo solo puede ser 0 o 1. Si queda un acarreo final después de la columna más significativa, necesariamente vale 1, y ese dígito extra también es impar.
De aquí sale la regla de paridad usada por las implementaciones: si el acarreo entrante es 0, la suma reflejada debe ser impar; si el acarreo entrante es 1, esa suma debe ser par.
Sea \(h=\lfloor L/2\rfloor\) y definamos
$$s_j=x_j+x_{L-1-j}\qquad (0\le j \lt h).$$
Lo importante para contar no es el par ordenado exacto de dígitos, sino su suma y cuántos pares producen esa suma. Para el par exterior ambos dígitos deben ser no nulos, así que
$$O(s)=\#\{(a,b)\in\{1,\dots,9\}^2:a+b=s\}.$$
En los pares interiores se permite el 0, de modo que
$$I(s)=\#\{(a,b)\in\{0,\dots,9\}^2:a+b=s\}.$$
En forma explícita,
$$O(s)=\begin{cases} s-1,&2\le s\le 10,\\ 19-s,&11\le s\le 18,\\ 0,&\text{en otro caso,} \end{cases} \qquad I(s)=\begin{cases} s+1,&0\le s\le 9,\\ 19-s,&10\le s\le 18,\\ 0,&\text{en otro caso.} \end{cases}$$
Por tanto, un patrón \((s_0,\dots,s_{h-1})\) tiene peso \(O(s_0)\prod_{j=1}^{h-1} I(s_j)\). Si \(L\) es impar, además se elige un dígito central \(m\), cuya columna aporta \(2m\).
Para \(L\) par, la secuencia de sumas por columna es
$$s_0,s_1,\dots,s_{h-1},s_{h-1},\dots,s_1,s_0,$$
mientras que para \(L\) impar es
$$s_0,s_1,\dots,s_{h-1},2m,s_{h-1},\dots,s_1,s_0.$$
La misma suma \(s_j\) aparece dos veces. Por eso, el acarreo que entra en su primera aparición y el que entra en su aparición reflejada deben coincidir; si no, la misma suma tendría que ser impar en una posición y par en la otra. Comparando la primera mitad con la segunda mitad reflejada se obtiene
$$c_{j+1}=c_{j-1}\qquad (1\le j \lt h).$$
Es decir, el patrón de acarreos al avanzar hacia el centro tiene período 2. Ese es el invariante decisivo del problema.
Sea \(L=2k\). El par reflejado central se usa en dos columnas consecutivas, así que sus dos acarreos entrantes deben coincidir. Junto con \(c_{j+1}=c_{j-1}\) y \(c_0=0\), esto fuerza
$$c_0=c_1=\cdots=c_k=0.$$
En consecuencia, toda suma reflejada debe ser impar y estrictamente menor que 10. Una suma impar mayor crearía un acarreo y rompería inmediatamente el patrón de ceros. El par exterior tiene entonces 20 elecciones, procedentes de las sumas impares \(3,5,7,9\) con multiplicidades \(2,4,6,8\). Cada par interior tiene 30 elecciones, procedentes de las sumas impares \(1,3,5,7,9\) con multiplicidades \(2,4,6,8,10\).
Por lo tanto, el número de reversibles de \(2k\) cifras es
$$R_{2k}=20\cdot 30^{k-1}.$$
En el rango pedido esto da
$$R_2=20,\qquad R_4=600,\qquad R_6=18000,\qquad R_8=540000.$$
Sea \(L=2k+1\). La columna central es \(2m+c_k\). Como \(2m\) es par y el dígito producido debe ser impar, necesariamente
$$c_k=1.$$
Pero la recurrencia \(c_{j+1}=c_{j-1}\), junto con \(c_0=0\), obliga a que los acarreos alternen:
$$0,1,0,1,\dots.$$
Así, \(c_k=1\) solo es posible cuando \(k\) es impar, es decir, exactamente cuando \(L\equiv 3 \pmod 4\). Esto prueba que las longitudes \(1,5,9,\dots\) no aportan nada.
Cuando \(L=4m+3\), ese patrón alternante fija por completo qué sumas están permitidas. El par exterior debe pasar de acarreo 0 a acarreo 1, así que su suma debe ser impar y al menos 11, lo que da 20 elecciones. Cada paso interior de 1 a 0 necesita una suma par menor que 10, lo que da 25 elecciones. Cada paso interior de 0 a 1 necesita una suma impar mayor que 10, lo que da 20 elecciones. El dígito central debe satisfacer \(2m+1 \lt 10\), así que hay 5 elecciones.
En consecuencia,
$$R_{4m+3}=20\cdot(25\cdot 20)^m\cdot 5=100\cdot 500^m,\qquad R_{4m+1}=0.$$
Debajo de \(10^9\), esto produce
$$R_3=100,\qquad R_7=50000,\qquad R_5=R_9=0.$$
El número de 2 cifras \(36\) es reversible porque \(36+63=99\). La única suma reflejada es \(3+6=9\), que es impar y menor que 10, así que ninguna columna genera acarreo.
El número de 3 cifras \(219\) también es reversible porque \(219+912=1131\). La suma exterior es \(2+9=11\), así que el patrón de acarreo empieza \(0\to 1\). La columna central vale \(2\cdot 1+1=3\), lo que hace volver el acarreo a 0. La última columna exterior vuelve a aportar 11 y genera el 1 inicial. Todos los dígitos de \(1131\) son impares, exactamente como predice el análisis.
La suma de las contribuciones no nulas por debajo de \(10^9\) es
$$20+100+600+18000+50000+540000=608720.$$
Las implementaciones en C++, Python y Java no recorren uno por uno todos los enteros menores que mil millones. En su lugar, construyen directamente el conteo combinatorio a partir de las sumas de pares reflejados.
Primero se cuenta, para cada suma entre 0 y 18, cuántos pares ordenados de dígitos la producen. Una tabla corresponde al par exterior, con dígitos en \(\{1,\dots,9\}\). La otra corresponde a los pares interiores, con dígitos en \(\{0,\dots,9\}\). De esa manera, muchas asignaciones concretas de dígitos quedan comprimidas en un solo estado ponderado.
Para cada longitud entre 2 y 9, la implementación elige recursivamente la secuencia \((s_0,\dots,s_{h-1})\). Cada vez que se fija una nueva suma reflejada, el peso acumulado se multiplica por la cantidad de pares de dígitos que la realizan. En longitudes impares también se prueban los 10 posibles dígitos centrales.
Una vez elegido un patrón de sumas, la implementación reconstruye la secuencia de columnas \(s_0,\dots,s_{h-1},2m,s_{h-1},\dots,s_0\) cuando hace falta y simula la suma de derecha a izquierda. Si aparece un dígito par, el patrón se descarta de inmediato. Si todos los dígitos son impares, su peso acumulado se añade al total. La versión en C++ también incluye comprobaciones pequeñas como \(R_2=20\), \(R_3=100\) y \(R_7=50000\) para verificar la lógica.
El código implementa literalmente la matemática anterior: los pares de dígitos reflejados se reducen a estados de suma, la recurrencia de acarreos se evalúa sin aproximaciones, y las multiplicidades cuentan todas las elecciones concretas de dígitos. Las fórmulas cerradas \(20\cdot 30^{k-1}\) y \(100\cdot 500^m\) son consecuencias de esas reglas, no hipótesis añadidas.
Para una longitud fija \(L\), la búsqueda recorre como mucho \(19^{\lfloor L/2\rfloor}\) patrones de sumas reflejadas, con un factor adicional de 10 en longitudes impares por el dígito central. Cada patrón completo se verifica en \(O(L)\) mediante la simulación de acarreos. Por tanto, la complejidad genérica por longitud es
$$O\!\left(L\cdot 19^{\lfloor L/2\rfloor}\right),$$
y el uso de memoria es \(O(L)\) para el patrón actual y el recorrido de acarreos.
Aquí \(L\le 9\), así que el tiempo real es diminuto. Desde el punto de vista matemático, una vez reconocidos los invariantes de acarreo, la respuesta incluso puede escribirse en forma cerrada; las implementaciones mantienen la DFS ponderada porque es corta, exacta y, para este rango, prácticamente de tiempo constante.
如果正整数 \(n\) 满足 \(n+\operatorname{rev}(n)\) 的每一位都是奇数，并且 \(n\) 与它的反转数都不允许出现前导零，那么称 \(n\) 为可逆数。对“小于 \(10^9\)”这个范围来说，必须统计 1 位到 9 位的所有可能长度，同时自动排除末位为 0 的数。
这个问题真正决定成败的不是枚举整数本身，而是十进制加法中的进位结构。把数字按左右对称的方式配成镜像对以后，问题就变成了一个有限的组合计数：统计哪些“镜像位和”与进位状态能够在每一列都产生奇数字。
把一个 \(L\) 位数写成
$$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0.$$
其中 \(x_0\neq 0\) 正好对应“反转后不能以 0 开头”。整个推导都来自对 \(n+\operatorname{rev}(n)\) 的逐列分析。
第 \(i\) 列相加的是镜像位置上的两个数字 \(x_i\) 和 \(x_{L-1-i}\)。设进入这一列的进位为 \(c_i\)，并令 \(c_0=0\)。定义
$$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor.$$
可逆性的要求是每个可见数字 \(d_i\) 都为奇数。由于始终有 \(x_i+x_{L-1-i}\le 18\)，所以每一步进位只能是 0 或 1。最高位之后如果还剩一个最终进位，它也只能是 1，而额外生成的前导位 1 仍然是奇数，因此不会破坏条件。
这立刻给出实现中使用的奇偶规则：如果进入当前列的进位是 0，那么镜像位和必须是奇数；如果进入当前列的进位是 1，那么镜像位和必须是偶数。
记 \(h=\lfloor L/2\rfloor\)，定义镜像位和
$$s_j=x_j+x_{L-1-j}\qquad (0\le j \lt h).$$
真正需要统计的不是某个具体有序数字对，而是它们的和，以及能产生该和的数字对个数。对最外层那一对来说，两位都不能为 0，因此
$$O(s)=\#\{(a,b)\in\{1,\dots,9\}^2:a+b=s\}.$$
对内部的镜像对来说，0 是允许的，因此
$$I(s)=\#\{(a,b)\in\{0,\dots,9\}^2:a+b=s\}.$$
这两个计数函数可以直接写成
$$O(s)=\begin{cases} s-1,&2\le s\le 10,\\ 19-s,&11\le s\le 18,\\ 0,&\text{其他情况,} \end{cases} \qquad I(s)=\begin{cases} s+1,&0\le s\le 9,\\ 19-s,&10\le s\le 18,\\ 0,&\text{其他情况。} \end{cases}$$
因此，一个和模式 \((s_0,\dots,s_{h-1})\) 的权重是 \(O(s_0)\prod_{j=1}^{h-1} I(s_j)\)。如果 \(L\) 是奇数，还要再选择一个中间数字 \(m\)，它在中心列中贡献 \(2m\)。
当 \(L\) 为偶数时，列和的顺序是
$$s_0,s_1,\dots,s_{h-1},s_{h-1},\dots,s_1,s_0,$$
当 \(L\) 为奇数时，顺序变为
$$s_0,s_1,\dots,s_{h-1},2m,s_{h-1},\dots,s_1,s_0.$$
同一个 \(s_j\) 会出现两次。于是，进入它第一次出现时的进位必须和进入镜像位置时的进位相同；否则同一个和会在一处被要求是奇数，在另一处被要求是偶数，这是不可能的。把前半段与后半段对应起来，可以得到
$$c_{j+1}=c_{j-1}\qquad (1\le j \lt h).$$
也就是说，从外向内走时，进位模式的周期是 2。这正是整个题目的核心不变量。
设 \(L=2k\)。最靠近中心的镜像对会在相邻两列中连续出现，所以这两次出现的进入进位必须相同。再结合 \(c_{j+1}=c_{j-1}\) 和 \(c_0=0\)，便得到
$$c_0=c_1=\cdots=c_k=0.$$
因此，每个镜像位和都必须是奇数并且严格小于 10。若某个奇和大于等于 11，就会产生进位，立刻破坏全 0 的进位模式。最外层那一对有 20 种选择，对应奇和 \(3,5,7,9\) 的重数 \(2,4,6,8\)；每个内部镜像对有 30 种选择，对应奇和 \(1,3,5,7,9\) 的重数 \(2,4,6,8,10\)。
所以，\(2k\) 位可逆数的总数为
$$R_{2k}=20\cdot 30^{k-1}.$$
在本题范围内，这给出
$$R_2=20,\qquad R_4=600,\qquad R_6=18000,\qquad R_8=540000.$$
设 \(L=2k+1\)。中心列的值是 \(2m+c_k\)。因为 \(2m\) 一定是偶数，而中心列生成的数字必须是奇数，所以必有
$$c_k=1.$$
但递推关系 \(c_{j+1}=c_{j-1}\) 再加上初始条件 \(c_0=0\)，会强迫进位沿着前半段交替出现：
$$0,1,0,1,\dots.$$
因此，只有当 \(k\) 为奇数时，才可能在中心得到 \(c_k=1\)，也就是只有 \(L\equiv 3 \pmod 4\) 的奇数长度可能成功。这立刻说明 \(1,5,9,\dots\) 位的情况全部为 0。
当 \(L=4m+3\) 时，这种交替模式会完全决定每个镜像位和的类型。最外层一对必须把进位从 0 推到 1，所以它的和必须是至少 11 的奇数，共 20 种。每个从进位 1 变回 0 的内部步骤需要一个小于 10 的偶和，共 25 种。每个从进位 0 变成 1 的内部步骤需要一个大于 10 的奇和，共 20 种。中心数字还必须满足 \(2m+1 \lt 10\)，因此有 5 种选择。
于是得到
$$R_{4m+3}=20\cdot(25\cdot 20)^m\cdot 5=100\cdot 500^m,\qquad R_{4m+1}=0.$$
在 \(10^9\) 以下，具体就是
$$R_3=100,\qquad R_7=50000,\qquad R_5=R_9=0.$$
两位数 \(36\) 是可逆数，因为 \(36+63=99\)。它唯一的镜像位和是 \(3+6=9\)，既是奇数，又小于 10，因此两列都不会产生进位。
三位数 \(219\) 也是可逆数，因为 \(219+912=1131\)。外层位和是 \(2+9=11\)，所以进位模式从 \(0\to 1\) 开始。中心列的值是 \(2\cdot 1+1=3\)，于是进位又回到 0。最后一列外层位和再次给出 11，并产生最前面的 1。整个结果 \(1131\) 的每一位都是奇数，和前面的进位分析完全一致。
把所有非零长度贡献相加，就得到 \(10^9\) 以下的总数
$$20+100+600+18000+50000+540000=608720.$$
C++、Python 和 Java 实现并不会暴力检查十亿以内的每个整数。它们直接按照上面的组合结构来计数。
实现首先统计 0 到 18 的每个和分别能由多少个有序数字对产生。一张表对应最外层镜像对，数字来自 \(\{1,\dots,9\}\)；另一张表对应内部镜像对，数字来自 \(\{0,\dots,9\}\)。这样，大量具体的数字选择就被压缩成了一个带权状态。
对 2 到 9 的每一种长度，程序递归枚举 \((s_0,\dots,s_{h-1})\) 这条镜像位和序列。每确定一个新的位和，就把当前权重乘上能够产生该和的数字对个数。若长度为奇数，还会额外枚举 10 个可能的中心数字。
当一个位和模式被完整选定后，程序会按需要重建列和序列 \(s_0,\dots,s_{h-1},2m,s_{h-1},\dots,s_0\)，然后从低位到高位模拟加法。如果某一列生成了偶数字，这个模式立刻被丢弃；如果所有列都生成奇数字，就把该模式的权重加入答案。C++ 版本还保留了 \(R_2=20\)、\(R_3=100\)、\(R_7=50000\) 等小型检查值，用来验证逻辑没有偏差。
代码并没有使用与数学推导不同的技巧。它做的事情正是：把镜像数字对压缩成和状态，精确执行进位递推，再用重数恢复所有具体的数字选择。闭式公式 \(20\cdot 30^{k-1}\) 与 \(100\cdot 500^m\) 只是这些规则的结论，而不是额外假设。
对固定长度 \(L\) 而言，程序最多枚举 \(19^{\lfloor L/2\rfloor}\) 个镜像位和模式；奇数长度还要为中心数字额外乘上一个 10。每个完整模式都要用 \(O(L)\) 时间做一次进位扫描，因此每种长度的通用复杂度为
$$O\!\left(L\cdot 19^{\lfloor L/2\rfloor}\right),$$
空间复杂度为 \(O(L)\)，用于保存当前模式和执行进位检查。
在本题中 \(L\le 9\)，所以实际运行量非常小。从纯数学角度看，一旦识别出进位不变量，答案甚至可以直接写成闭式；实现保留带权 DFS，是因为它简洁、精确，而且对这个范围来说已经等同于常数时间。
Положительное целое число \(n\) называется обратимым, если все цифры числа \(n+\operatorname{rev}(n)\) нечётные, причём ни у самого \(n\), ни у его перевёрнутой записи не должно появляться ведущих нулей. Для диапазона ниже \(10^9\) это означает, что нужно рассмотреть все длины от 1 до 9 и сразу отбросить числа, оканчивающиеся нулём.
Ключевой факт в том, что всё определяется переносами в десятичном сложении. Если сгруппировать цифры в зеркальные пары, задача перестаёт быть перебором миллиардов чисел и превращается в конечный комбинаторный подсчёт по суммам пар цифр и состояниям переноса.
Запишем \(L\)-значное число в виде
$$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0.$$
Условие \(x_0\neq 0\) как раз и означает, что перевёрнутое число не может начинаться с нуля. Вся конструкция решения строится на поколоночном анализе суммы \(n+\operatorname{rev}(n)\).
В столбце \(i\) складываются зеркальные цифры \(x_i\) и \(x_{L-1-i}\). Пусть входящий перенос равен \(c_i\), а \(c_0=0\). Тогда
$$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor.$$
Обратимость означает, что каждая видимая цифра \(d_i\) нечётна. Поскольку всегда \(x_i+x_{L-1-i}\le 18\), любой перенос может быть только 0 или 1. Если после старшего столбца остаётся финальный перенос, то это обязательно 1, а значит и дополнительная ведущая цифра тоже нечётна.
Отсюда немедленно следует правило чётности, на котором основаны реализации: если входящий перенос равен 0, то сумма зеркальной пары должна быть нечётной; если входящий перенос равен 1, то эта сумма должна быть чётной.
Положим \(h=\lfloor L/2\rfloor\) и введём суммы зеркальных пар
$$s_j=x_j+x_{L-1-j}\qquad (0\le j \lt h).$$
Для подсчёта важна не сама упорядоченная пара цифр, а только её сумма и число способов получить эту сумму. Для внешней пары обе цифры должны быть ненулевыми, поэтому
$$O(s)=\#\{(a,b)\in\{1,\dots,9\}^2:a+b=s\}.$$
Для внутренних пар нули разрешены, поэтому
$$I(s)=\#\{(a,b)\in\{0,\dots,9\}^2:a+b=s\}.$$
Явно это выглядит так:
$$O(s)=\begin{cases} s-1,&2\le s\le 10,\\ 19-s,&11\le s\le 18,\\ 0,&\text{иначе,} \end{cases} \qquad I(s)=\begin{cases} s+1,&0\le s\le 9,\\ 19-s,&10\le s\le 18,\\ 0,&\text{иначе.} \end{cases}$$
Следовательно, выбранный шаблон \((s_0,\dots,s_{h-1})\) имеет вес \(O(s_0)\prod_{j=1}^{h-1} I(s_j)\). Если \(L\) нечётно, дополнительно выбирается центральная цифра \(m\), которая даёт вклад \(2m\) в средний столбец.
При чётном \(L\) последовательность столбцовых сумм имеет вид
$$s_0,s_1,\dots,s_{h-1},s_{h-1},\dots,s_1,s_0,$$
а при нечётном \(L\) вид
$$s_0,s_1,\dots,s_{h-1},2m,s_{h-1},\dots,s_1,s_0.$$
Одна и та же сумма \(s_j\) встречается дважды. Поэтому перенос, входящий в её первое появление, должен совпадать с переносом, входящим в зеркальное появление; иначе одна и та же сумма должна была бы быть нечётной в одном месте и чётной в другом. Сопоставление первой половины со второй даёт
$$c_{j+1}=c_{j-1}\qquad (1\le j \lt h).$$
Значит, шаблон переносов по пути к центру имеет период 2. Это и есть главный инвариант всей задачи.
Пусть \(L=2k\). Центральная зеркальная пара используется в двух соседних столбцах, поэтому входящие в них переносы обязаны совпадать. Вместе с \(c_{j+1}=c_{j-1}\) и \(c_0=0\) это даёт
$$c_0=c_1=\cdots=c_k=0.$$
Следовательно, каждая зеркальная сумма должна быть нечётной и строго меньше 10. Большая нечётная сумма породила бы перенос и сразу разрушила бы нулевой шаблон. Внешняя пара тогда имеет 20 вариантов: суммы \(3,5,7,9\) с кратностями \(2,4,6,8\). Каждая внутренняя пара имеет 30 вариантов: суммы \(1,3,5,7,9\) с кратностями \(2,4,6,8,10\).
Поэтому число обратимых чисел длины \(2k\) равно
$$R_{2k}=20\cdot 30^{k-1}.$$
В рассматриваемом диапазоне это даёт
$$R_2=20,\qquad R_4=600,\qquad R_6=18000,\qquad R_8=540000.$$
Пусть \(L=2k+1\). Средний столбец имеет вид \(2m+c_k\). Так как \(2m\) всегда чётно, а получающаяся цифра должна быть нечётной, необходимо
$$c_k=1.$$
Но рекурсия \(c_{j+1}=c_{j-1}\) вместе с условием \(c_0=0\) заставляет переносы чередоваться:
$$0,1,0,1,\dots.$$
Значит, \(c_k=1\) возможно только тогда, когда \(k\) нечётно, то есть именно при \(L\equiv 3 \pmod 4\). Отсюда сразу следует, что длины \(1,5,9,\dots\) не дают ни одного числа.
Когда \(L=4m+3\), это чередование полностью определяет допустимые типы сумм. Внешняя пара должна перевести перенос из 0 в 1, значит её сумма должна быть нечётной и не меньше 11, что даёт 20 вариантов. Каждый внутренний шаг из 1 в 0 требует чётную сумму меньше 10, то есть 25 вариантов. Каждый внутренний шаг из 0 в 1 требует нечётную сумму больше 10, то есть 20 вариантов. Центральная цифра должна удовлетворять \(2m+1 \lt 10\), значит вариантов 5.
Следовательно,
$$R_{4m+3}=20\cdot(25\cdot 20)^m\cdot 5=100\cdot 500^m,\qquad R_{4m+1}=0.$$
Ниже \(10^9\) это означает
$$R_3=100,\qquad R_7=50000,\qquad R_5=R_9=0.$$
Двузначное число \(36\) обратимо, потому что \(36+63=99\). Единственная зеркальная сумма равна \(3+6=9\); она нечётна и меньше 10, поэтому ни в одном столбце не возникает перенос.
Трёхзначное число \(219\) тоже обратимо, потому что \(219+912=1131\). Внешняя сумма равна \(2+9=11\), поэтому шаблон переносов начинается как \(0\to 1\). Средний столбец равен \(2\cdot 1+1=3\) и возвращает перенос к 0. Последний внешний столбец снова даёт 11 и создаёт ведущую единицу. Все цифры числа \(1131\) нечётны, ровно как предсказывает анализ переносов.
Суммируя ненулевые вклады, получаем общее число ниже \(10^9\):
$$20+100+600+18000+50000+540000=608720.$$
Реализации на C++, Python и Java не перебирают по одному все числа меньше миллиарда. Вместо этого они напрямую считают количество допустимых конфигураций зеркальных сумм.
Сначала программа подсчитывает, сколько упорядоченных пар цифр дают каждую сумму от 0 до 18. Одна таблица относится к внешней паре, где обе цифры берутся из \(\{1,\dots,9\}\). Другая относится к внутренним парам, где разрешены цифры из \(\{0,\dots,9\}\). Благодаря этому множество конкретных чисел сворачивается в один взвешенный state.
Для каждой длины от 2 до 9 реализация рекурсивно выбирает последовательность \((s_0,\dots,s_{h-1})\). При каждом выборе новой зеркальной суммы текущий вес умножается на число пар цифр, реализующих эту сумму. Для нечётных длин отдельно перебираются все 10 возможных центральных цифр.
Когда шаблон сумм полностью задан, программа при необходимости восстанавливает последовательность столбцов \(s_0,\dots,s_{h-1},2m,s_{h-1},\dots,s_0\) и моделирует сложение справа налево. Если хотя бы один получившийся разряд чётен, шаблон немедленно отбрасывается. Иначе его накопленный вес добавляется к ответу. В версии на C++ дополнительно присутствуют контрольные значения \(R_2=20\), \(R_3=100\) и \(R_7=50000\), служащие проверкой корректности.
Код буквально реализует описанную математику: зеркальные пары цифр сжимаются в состояния по суммам, рекурсия переносов вычисляется точно, а кратности учитывают все конкретные назначения цифр. Закрытые формулы \(20\cdot 30^{k-1}\) и \(100\cdot 500^m\) являются следствием этих правил, а не внешними догадками.
Для фиксированной длины \(L\) перебирается не более \(19^{\lfloor L/2\rfloor}\) шаблонов зеркальных сумм; для нечётных длин добавляется множитель 10 из-за центральной цифры. Каждый завершённый шаблон проверяется за \(O(L)\) путём моделирования переносов. Поэтому общая оценка на одну длину такова:
$$O\!\left(L\cdot 19^{\lfloor L/2\rfloor}\right),$$
а память составляет \(O(L)\) для хранения текущего шаблона и проверки переносов.
Здесь \(L\le 9\), поэтому реальное время работы очень мало. С математической точки зрения, после распознавания инвариантов переноса ответ можно записать и в закрытом виде; реализации сохраняют взвешенный DFS, потому что он короткий, точный и для данного диапазона практически константный по времени.
يُسمّى العدد الصحيح الموجب \(n\) قابلاً للعكس إذا كان \(n+\operatorname{rev}(n)\) مكوَّناً بالكامل من أرقام فردية، مع الشرط الإضافي أن لا يكتسب \(n\) ولا معكوسه الصفري أصفاراً بادئة. وتحت الحد \(10^9\) يعني ذلك أننا نعد جميع الأطوال من 1 إلى 9 أرقام، مع استبعاد كل عدد ينتهي بصفر.
الفكرة الحاسمة أن الخاصية كلها يحكمها انتقال الحمل في الجمع العشري. وما إن نجمع الأرقام في أزواج متناظرة حول الوسط حتى تتحول المسألة من فحص مليارات الأعداد إلى عدّ تركيبي محدود على مجاميع الأزواج وحالات الحمل.
لنكتب عدداً من \(L\) أرقام على الصورة
$$n=\sum_{i=0}^{L-1} x_i 10^i,\qquad x_{L-1}\neq 0,\qquad x_0\neq 0.$$
الشرط \(x_0\neq 0\) هو بالضبط منع المعكوس من أن يبدأ بصفر. وكل البرهان يأتي من تحليل \(n+\operatorname{rev}(n)\) عموداً بعد عمود.
في العمود \(i\) نجمع الرقمين المتناظرين \(x_i\) و\(x_{L-1-i}\). إذا كان الحمل الداخل هو \(c_i\) ومع \(c_0=0\)، فنعرّف
$$t_i=x_i+x_{L-1-i}+c_i,\qquad d_i=t_i \bmod 10,\qquad c_{i+1}=\left\lfloor\frac{t_i}{10}\right\rfloor.$$
كون العدد قابلاً للعكس يعني أن كل رقم ظاهر \(d_i\) يجب أن يكون فردياً. وبما أن \(x_i+x_{L-1-i}\le 18\) دائماً، فإن كل حمل لا يمكن أن يكون إلا 0 أو 1. وإذا بقي حمل نهائي بعد العمود الأعلى قيمة، فلا بد أن يكون 1، وهذا الرقم الإضافي نفسه فردي، فلا يسبب مشكلة.
ومن هنا تظهر قاعدة الزوجية الأساسية التي تعتمدها التطبيقات: إذا كان الحمل الداخل 0، فيجب أن يكون مجموع الزوج المتناظر فردياً؛ وإذا كان الحمل الداخل 1، فيجب أن يكون هذا المجموع زوجياً.
لتكن \(h=\lfloor L/2\rfloor\)، ولنعرّف مجاميع الأزواج المتناظرة
$$s_j=x_j+x_{L-1-j}\qquad (0\le j \lt h).$$
المهم في العد ليس الزوج المرتب نفسه، بل مجموعه وعدد الأزواج التي تعطي هذا المجموع. في الزوج الخارجي يجب أن يكون الرقمان غير صفريين، ولذلك
$$O(s)=\#\{(a,b)\in\{1,\dots,9\}^2:a+b=s\}.$$
أما الأزواج الداخلية فيُسمح فيها بالصفر، ولذلك
$$I(s)=\#\{(a,b)\in\{0,\dots,9\}^2:a+b=s\}.$$
وصيغتا التعداد هما
$$O(s)=\begin{cases} s-1,&2\le s\le 10,\\ 19-s,&11\le s\le 18,\\ 0,&\text{otherwise,} \end{cases} \qquad I(s)=\begin{cases} s+1,&0\le s\le 9,\\ 19-s,&10\le s\le 18,\\ 0,&\text{otherwise.} \end{cases}$$
وعليه فإن وزن النمط \((s_0,\dots,s_{h-1})\) يساوي \(O(s_0)\prod_{j=1}^{h-1} I(s_j)\). وإذا كان \(L\) فردياً، نختار أيضاً رقماً وسطياً \(m\) فتكون مساهمة العمود الأوسط \(2m\).
إذا كان \(L\) زوجياً فترتيب مجاميع الأعمدة هو
$$s_0,s_1,\dots,s_{h-1},s_{h-1},\dots,s_1,s_0,$$
وإذا كان \(L\) فردياً يصبح
$$s_0,s_1,\dots,s_{h-1},2m,s_{h-1},\dots,s_1,s_0.$$
القيمة نفسها \(s_j\) تظهر مرتين. لذلك يجب أن يكون الحمل الداخل إلى ظهورها الأول مساوياً للحمل الداخل إلى ظهورها المنعكس؛ وإلا لاضطرت القيمة نفسها أن تكون فردية في موضع وزوجية في موضع آخر. وعند مطابقة النصف الأول بالنصف الثاني المنعكس نحصل على
$$c_{j+1}=c_{j-1}\qquad (1\le j \lt h).$$
أي إن نمط الحمل في طريقه نحو الوسط دوري بفترة 2. وهذا هو الثابت الأساسي في المسألة كلها.
لنأخذ \(L=2k\). الزوج المتناظر الأقرب إلى الوسط يُستخدم في عمودين متتاليين، ولذلك يجب أن يتساوى الحمل الداخل إلى هذين العمودين. ومع \(c_{j+1}=c_{j-1}\) و\(c_0=0\) ينتج
$$c_0=c_1=\cdots=c_k=0.$$
إذن يجب أن يكون كل مجموع متناظر فردياً وأصغر من 10. فأي مجموع فردي أكبر من ذلك سينتج حملاً ويكسر مباشرة نمط الأصفار. للزوج الخارجي 20 اختياراً، ناتجة من المجاميع الفردية \(3,5,7,9\) بتكرارات \(2,4,6,8\). ولكل زوج داخلي 30 اختياراً، ناتجة من المجاميع الفردية \(1,3,5,7,9\) بتكرارات \(2,4,6,8,10\).
ومن ثم يكون عدد الأعداد القابلة للعكس ذات \(2k\) أرقام هو
$$R_{2k}=20\cdot 30^{k-1}.$$
وفي المجال المطلوب نحصل على
$$R_2=20,\qquad R_4=600,\qquad R_6=18000,\qquad R_8=540000.$$
إذا كان \(L=2k+1\)، فالعمود الأوسط يساوي \(2m+c_k\). ولأن \(2m\) زوجي دائماً والرقم الناتج يجب أن يكون فردياً، فلا بد أن يكون
$$c_k=1.$$
لكن العلاقة \(c_{j+1}=c_{j-1}\) مع الشرط الابتدائي \(c_0=0\) تفرض نمطاً متناوباً للحمل:
$$0,1,0,1,\dots.$$
ولذلك لا يمكن أن يتحقق \(c_k=1\) إلا إذا كان \(k\) فردياً، أي بالضبط عندما يكون \(L\equiv 3 \pmod 4\). وهذا يثبت فوراً أن الأطوال \(1,5,9,\dots\) لا تسهم بشيء.
وعندما يكون \(L=4m+3\)، يحدد هذا النمط المتناوب نوع كل مجموع مسموح. الزوج الخارجي يجب أن ينقل الحمل من 0 إلى 1، لذا يجب أن يكون مجموعه فردياً ولا يقل عن 11، وهذا يعطي 20 اختياراً. وكل خطوة داخلية من حمل 1 إلى حمل 0 تحتاج مجموعاً زوجياً أصغر من 10، أي 25 اختياراً. وكل خطوة داخلية من حمل 0 إلى حمل 1 تحتاج مجموعاً فردياً أكبر من 10، أي 20 اختياراً. أما الرقم الأوسط فيجب أن يحقق \(2m+1 \lt 10\)، ولذلك توجد 5 اختيارات.
إذن
$$R_{4m+3}=20\cdot(25\cdot 20)^m\cdot 5=100\cdot 500^m,\qquad R_{4m+1}=0.$$
وتحت \(10^9\) يعطي هذا
$$R_3=100,\qquad R_7=50000,\qquad R_5=R_9=0.$$
العدد المكوّن من رقمين \(36\) قابل للعكس لأن \(36+63=99\). المجموع المتناظر الوحيد هو \(3+6=9\)، وهو فردي وأصغر من 10، ولذلك لا يتولد أي حمل في أي عمود.
والعدد ذو الثلاثة أرقام \(219\) قابل للعكس أيضاً لأن \(219+912=1131\). المجموع الخارجي هو \(2+9=11\)، ومن ثم يبدأ نمط الحمل على الصورة \(0\to 1\). العمود الأوسط يساوي \(2\cdot 1+1=3\)، فيعيد الحمل إلى 0. ثم يعطي العمود الخارجي الأخير 11 مرة أخرى وينتج الواحد في المقدمة. وبذلك تكون كل أرقام \(1131\) فردية كما يتنبأ التحليل تماماً.
وبجمع المساهمات غير الصفرية نحصل على العدد الكلي تحت \(10^9\):
$$20+100+600+18000+50000+540000=608720.$$
تنفيذات C++ وPython وJava لا تفحص كل عدد أصغر من مليار فحصاً مباشراً. بل تبني العدّ التركيبي مباشرة من مجاميع الأزواج المتناظرة.
تبدأ التنفيذات بحساب عدد الأزواج المرتبة التي تعطي كل مجموع من 0 إلى 18. يوجد جدول خاص بالزوج الخارجي حيث تؤخذ الأرقام من \(\{1,\dots,9\}\)، وجدول آخر للأزواج الداخلية حيث تؤخذ الأرقام من \(\{0,\dots,9\}\). وبذلك تُضغط أعداد كثيرة مختلفة إلى حالة واحدة ذات وزن عددي.
لكل طول من 2 إلى 9، تختار التنفيذات السلسلة \((s_0,\dots,s_{h-1})\) اختياراً تراجعياً. وفي كل مرة يُختار فيها مجموع متناظر جديد، يُضرب الوزن الجاري في عدد أزواج الأرقام التي تحقق هذا المجموع. وفي الأطوال الفردية تُجرَّب أيضاً جميع الأرقام الوسطى العشرة الممكنة.
بعد اكتمال اختيار نمط المجاميع، تعيد التنفيذات بناء تسلسل الأعمدة \(s_0,\dots,s_{h-1},2m,s_{h-1},\dots,s_0\) عند الحاجة، ثم تحاكي الجمع من اليمين إلى اليسار. فإذا ظهر رقم زوجي في أي عمود رُفض النمط فوراً. وإذا كانت جميع الأرقام الناتجة فردية، أُضيف وزنه إلى الجواب النهائي. كما أن نسخة C++ تتضمن قيم تحقق صغيرة مثل \(R_2=20\) و\(R_3=100\) و\(R_7=50000\) للتأكد من صحة المنطق.
الكود يطبق الرياضيات السابقة مباشرة: يختزل الأزواج المتناظرة إلى حالات تمثل المجاميع، ويقيّم علاقة الحمل بدقة، ثم يستعيد كل الاختيارات الفعلية للأرقام عبر الأوزان. والصيغ المغلقة \(20\cdot 30^{k-1}\) و\(100\cdot 500^m\) ليست فرضيات منفصلة، بل نتائج مباشرة لهذه القواعد.
لطول ثابت \(L\)، يستكشف البرنامج في أقصى الأحوال \(19^{\lfloor L/2\rfloor}\) من أنماط المجاميع المتناظرة، مع عامل إضافي قدره 10 في الأطوال الفردية بسبب الرقم الأوسط. ويُفحص كل نمط مكتمل في زمن \(O(L)\) عبر محاكاة الحمل. لذلك يكون التعقيد العام لكل طول
$$O\!\left(L\cdot 19^{\lfloor L/2\rfloor}\right),$$
أما الذاكرة فهي \(O(L)\) لتخزين النمط الحالي ومسح الحمل.
وفي هذه المسألة لدينا \(L\le 9\)، لذا فالزمن الفعلي صغير جداً. ومن الناحية الرياضية يمكن كتابة الجواب بصيغة مغلقة فور فهم ثوابت الحمل؛ ومع ذلك تحتفظ التنفيذات بالبحث العمقي الموزون لأنه قصير ودقيق ويعمل هنا كما لو كان بزمن ثابت.