Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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.

Mirrored columns and the carry recurrence

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.

Compressing the search to pair sums

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\).

Symmetry forces a recurrence on the carries

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.

Even lengths: every carry is forced to be zero

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.$

Odd lengths: only \(L\equiv 3 \pmod 4\) can work

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.$

Worked examples

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.$

How the Code Works

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.

Multiplicity tables for 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.

Depth-first enumeration by length

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.

Carry validation of a completed pattern

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.

Why this matches the derivation

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: Project Euler 145
2. Carry in addition: Wikipedia - Carry (arithmetic)
3. Positional notation: Wikipedia - Positional notation
4. Parity: Wikipedia - Parity (mathematics)
5. Digit reversal: MathWorld - Digit Reversal