# 62'396 is a special number

When I was young, I once found an article in one of my father’s journals. The title was “62’396 is a special number”. Here’s why:

```
62396
6239
623
62
6
-----
69326
```

Adding the number with itself stepwise shifted to the right yields to original number reversed. The article went on saying that this is the only 5 digit number with this property. And the readers where invited to find more such numbers.

I took the challenge and worked on it for quite some time. In the end I came up with a program written in Turbo Pascal and inline Assembler.

It found all numbers up to about 12 digits. One of the bigger problems was that such big numbers don’t fit into 32 bit, which was the `long int`

data type at that time.

Strangely I remembered this story today and I decided to give it a try, 20 years afterwards.

I could reimplement my old algorithm in Python in about an hour. (NOT everything was better in the old days…)

It’s basically solving the equation

```
10000a + 1000b + 100c + 10d + e +
1000a + 100b + 10c + d +
100a + 10b + c +
10a + b +
a
= ---------------------------------
10000e + 1000d + 100c + 10b + a
```

simplifying this yields

```
11110a + 1101b + 11c - 989d - 9999e = 0
```

which can then be solved by brute force by trying out every combination of values between 0 and 9.

One optimization is ordering the terms by magnitude

```
11110a - 9999e + 1101b - 989d + 11c = 0
```

and calculate the maximum / minimum possible values for sub expressions. This gives tighter limits for the variables. E.g.

```
-98892 <= -9999e + 1101b - 989d + 11c <= 10008
```

so we only need to try values for `a`

which satisfy `-98892 <= 11110a <= 10008`

. This way we get the next few numbers

```
425274
33626373
44594594
2472527472
72207603208
44505405494
54494594506
26792396792
```

but finding more numbers gets slow pretty quickly. A more efficient algorithm is needed. The numbers look as if there is some hidden property behind them. There are lots of repeating digits and patterns. When I was young, I tried hard to find something, but I was not successful.

Today I had more luck.

Starting from the base equation

```
abcde +
abcd +
abc +
ab +
a =
-------
edcba
```

and looking at the rightmost column, it can be seen that `e + d + c + b = 10x`

for some unknown `x`

.

The algorithm starts with trying values for `a`

, then `e`

, then `b`

(ordered by the magnitude of their coefficients).

The second column to the right states that `(d + c + b + a + x) mod 10 = b`

. (`x`

is the carry over from the rightmost column.)

Using `d + c + b = 10x - e`

yields `(10x - e + a + x) mod 10 = b`

.

Because at this point, we already have values for `a`

and `e`

, given an `x`

we can calculate `b`

directly without any brute force.

The same trick can later be used to directly calculate `c`

.

So only half of the digits must be found by brute force, the other half can be calculated directly. In exchange we have to run the algorithm several times for all possible values of `x`

. But `1 <= x <= 0.9n`

where `n`

is the number of digits, in this case 5.

This is a huge improvement and now it’s possible to calculate all such numbers up to 60 digits in just a minute.

The (empiric) complexity analysis of the algorithms shows how well this idea works:

Algorithm | Complexity | Digits to add for 10x complexity |
---|---|---|

brute force | O(10^{n}) | 1 |

min / max | O(3.2^{n}) | 2 |

final | O(1.3^{n}) | 9 |

Nice little mathematics for a sunday afternoon… or rather night.