intro

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:: http://mathworld.wolfram.com/196-Algorithm.html; http://neuronio.mat.uc.pt/crcmath/math/math/0/0020.htm; http://mathworld.wolfram.com/PalindromicNumberConjecture.html; http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006960; http://www.seanet.com/~ksbrown/kmath004.htm; http://www.math.niu.edu/~rusin/known-math/96/palindrom.196; http://www.math.niu.edu/~rusin/known-math/96/palindrome
links:: http://www.ping.be/~ping6758/weblinks.htm; http://www.ping.be/~ping6758/intro.htm
message archives:: http://library.wolfram.com/mathgroup/archive/1999/Oct/msg00083.html; http://www-math.math.rwth-aachen.de/MapleAnswers/32.html
parallel implementation:: http://www.cs.uoregon.edu/~stephen/research/pCxx_vs_ZPL/palindrome.html
calculation story:: http://www.fourmilab.ch/documents/threeyears/two_months_more.html; http://www.fourmilab.ch/documents/threeyears/threeyears.html; http://www.extra.hu/bozsik/main.htm; http://www.floot.demon.co.uk/palindromes.html; http://schubert.univ-mlv.fr/~vince/ARTICLES/revpal.ps; http://www.tbaytel.net/~forslund/palindro.html
index sites:: http://www.quiltplace.com/Science/Math/Number_Theory/; http://www.dmoz.org/Science/Math/Number_Theory/
least squares calculation:: http://nimitz.mcs.kent.edu/~blewis/stat/lsq.html
puzzles faq:: arithmetic/digits/palindrome.p
Does the series formed by adding a number to its reversal always end in a palindrome?
arithmetic/digits/palindrome.s
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

option

description

use

-v[FSADI]

verbose

F	report on failed (non palindromic) numbers
S	report on success (palindromic) numbers
A	print all iteration steps
D	print number lengths for all iteration steps
C	print repeat counts for number lengths
I	print iteration number during search

-q[FSADI]

quiet

-l[filename]

enable logging to file

-nNUMBER

search until NUMBER

-mNUMBER

maximum number of iterations

-RNUMBER

generate <NUMBER> digit random numbers

for probing density of palindromic numbers

-rRANGE

radix range to search

-r2-16 searches all numberbases from 2 - 16

-sNUMBER

set random number seed

to 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_IMPLEMENTATION	like USE_C_IMPLEMENTATION
USE_ASM_IMPLEMENTATION2	(only bytes version), like USE_C_IMPLEMENTATION2
USE_ASM_IMPLEMENTATION3	use fixed bases + index iso pointers
USE_C_IMPLEMENTATION	original c implementation
USE_C_IMPLEMENTATION2	first loop for addition, second loop for div + carry

USE_IDIV	use idiv instruction
USE_TABLES	use 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

base	details	class starters
2	details	2:10110(simple), 2:1000010100110, 1110001010111
3	details	3:10211, 3:1000122, 3:1002211
4	details	4:10202, 4:10332(simple), 4:23033, 4:30123, 4:30133
5	details	5:10313, 5:10343
6	details	6: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
7	details	7:10513, 7:10525, 7:12165, 7:13364, 7:16164
8	details	8: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
9	details	9:728
10	details	10:196, 10:879
11	details
12	details
13	details
14	details
15	details
16	details

'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 version

improved 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
1000000000	116:334 06:05:40.796838

density of palindromic numbers

....