Detailed mathematical approach

Problem Summary

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.

Mathematical Approach

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

The Right State Space

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.

Why the Starting Number Does Not End the Search

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.

A Useful Digit-Growth Bound

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.

Worked Examples

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.

How the Code Works

Decimal-String Arithmetic Instead of Big Integers

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.

Testing One Start, Then Sweeping the Full Range

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.

Complexity Analysis

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.

Footnotes and References

1. Problem page: Project Euler 55 - Lychrel numbers
2. Lychrel numbers: Wikipedia - Lychrel number
3. Palindromic numbers: Wikipedia - Palindromic number
4. The reverse-and-add process: Wikipedia - 196-algorithm