This page is about a recreational math problem:
if you take a number, reverse its digits, add it to the original, and repeat.
Usually you will get a palindromic number after a few steps. Palidromic meaning the number equals it self with its digits reversed.
with '69' for example you will get 165, 726, 1353 and then 4884.
for 196 however this process does not seem to stop.
Since a lot of things show clearer patters when done in binary, I looked at the binary case, for some numbers (the first being 22) the pattern of repetition is obvious.
For better explanations see one of the pages below:

info elsewhere on the net

math encyclopidia:
message archives:
parallel implementation:
calculation story:
index sites:
least squares calculation:
puzzles faq:


Does the series formed by adding a number to its reversal always end in a palindrome?


This is not known.
If you start with 196, after 9480000 iterations you get a 3924257-digit non-palindromic number. However, there is no known proof that you will never get a palindrome.
The statement is provably false for binary numbers. Roland Sprague has shown that 10110 starts a series that never goes palindromic. -----------------------------------

my search program

Source is available here
java Source is available here

commandline options

-v[FSADI] verbose
Freport on failed (non palindromic) numbers
Sreport on success (palindromic) numbers
Aprint all iteration steps
Dprint number lengths for all iteration steps
Cprint repeat counts for number lengths
Iprint iteration number during search
-q[FSADI] quiet
-l[filename]enable logging to file
-nNUMBERsearch until NUMBER
-mNUMBERmaximum number of iterations
-RNUMBERgenerate <NUMBER> digit random numbersfor probing density of palindromic numbers
-rRANGEradix range to search-r2-16 searches all numberbases from 2 - 16
-sNUMBERset random number seedto make numbers generated with '-R' reproducable
dump196 -qFSAI -vD -m10000 10:196
will print the lengths of the first 10000 iteration steps of 196 in the decimal number system.
dump196 -qFSAI -vD -m10000 2:10110
will print the lengths of the first 10000 iteration steps of 22 in the binary number system.
dump196 -qDAIS -vF -r2-4 -n100 -m400
will search for non palindromic numbers in the binary, ternary en quartary number systems upto 100.
dump196 -qDAISF -vC -m10000 2:10110
will reveal the obvious regularity with which this number repeats
dump196 -qDAISF -vC -m10000 2:1110001010111
show that there are also binary numbers which show now apparent regularity.

number representation

Numbers upto base 62 can be printed, with digit values represented as follows:
0 - 9'0' - '9'
10 - 35'A' - 'Z' (uppercase letters)
36 - 61'a' - 'z' (lowercase letters)

compiler options

Several implementations can be used:
USE_BYTES, USE_WORDS, USE_LONGS to control what storage unit is used
USE_ASM_IMPLEMENTATION3use fixed bases + index iso pointers
USE_C_IMPLEMENTATIONoriginal c implementation
USE_C_IMPLEMENTATION2first loop for addition, second loop for div + carry
USE_IDIVuse idiv instruction
USE_TABLESuse tables with precalculated div results
for very large numbers the USE_C_IMPLEMENTATION is the fastest. for small numbers the USE_ASM_IMPLEMENTATION3 is the fastest

non palindromic number classes

basedetailsclass starters
2details2:10110(simple), 2:1000010100110, 1110001010111
3details3:10211, 3:1000122, 3:1002211
4details4:10202, 4:10332(simple), 4:23033, 4:30123, 4:30133
5details5:10313, 5:10343
6details6:4555, 6:10235, 6:10413, 6:12454, 6:13253, 6:14054, 6:14254, 6:25455, 6:40035, 6:40235, 6:101504, 6:101513, 6:102504, 6:102514, 6:104513, 6:104514, 6:104544, 6:105514, 6:105524, 6:105531
7details7:10513, 7:10525, 7:12165, 7:13364, 7:16164
8details8:1775, 8:7047, 8:10347, 8:10436, 8:10464, 8:10475, 8:10534, 8:10624, 8:10626, 8:10646, 8:10652(simple), 8:10660, 8:10662, 8:10737, 8:10760, 8:10762, 8:11775, 8:12576, 8:12775, 8:14176, 8:17176, 8:20067, 8:20637
10details10:196, 10:879
'simple' means these are obviously non palindromic numbers
To make detection of regularity in the iteration process easier, I took a look at how many consecutive steps the number of digits remains the same.
For a base G, a maximum of ceil(log(G)/log(2))+1 steps the number of digits remains the same.

runtime of calculations

the test program I wrote is quadratic in the number of iterations needed to perform. ( this is on a 366 Mhz Pentium 3)
t = 0.000000023686198151627892*n^2 +0.00000017293902259378747*n +0.0035041434755715595
update after some optimizing of my code (mainly avoiding the 'idiv' instruction) the timing is now calculated as:
t = 0.01306140350877207 -3.0146958304853008*10^(-6) * n + 3.6870585554796073*10^(-9) * n^2
old versionimproved version
iterations y:d h:m:s
1000 0:000 00:00:00.027363
10000 0:000 00:00:02.373853
100000 0:000 00:03:56.882779
1000000 0:000 06:34:46.374594
10000000 0:027 09:57:01.548057
100000000 7:186 10:59:58.813685
1000000000 751:030 19:32:04.570420
iterations y:d h:m:s
1000 0:000 00:00:00.013734
10000 0:000 00:00:00.351620
100000 0:000 00:00:36.582177
1000000 0:000 01:01:24.056921
10000000 0:004 06:24:35.721651
100000000 1:061 17:44:44.098274
1000000000116:334 06:05:40.796838

density of palindromic numbers