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:

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ⁿ)	1
min / max	O(3.2ⁿ)	2
final	O(1.3ⁿ)	9

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