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
The algorithm starts with trying values for
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.)
d + c + b = 10x - e yields
(10x - e + a + x) mod 10 = b.
Because at this point, we already have values for
e, given an
x we can calculate
b directly without any brute force.
The same trick can later be used to directly calculate
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
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|
|min / max||O(3.2n)||2|
Nice little mathematics for a sunday afternoon… or rather night.