On the 'Reverse and Add!' algorithm in base 2

         Klaus Brockhaus (klaus-brockhaus(AT)t-online.de)

                       04 Jun 2001

The 'Reverse and Add!' algorithm means: choose a nonnegative integer as
starting point, reverse the digits of the integer and add the result
to the original integer, and repeat these two operations indefinitely.
In this way the algorithm generates a sequence of integers for each
starting point integer, the trajectory of this integer. One may then ask
if the trajectory eventually reaches an integer that satisfies a
certain pre-specified condition, the stopping criterion.

The operation of addition is independent of the base for representing
the integers, but the operation of reversing is base dependent, and the
stopping criterion may or may not be base dependent. The base-dependent
palindrome property has been thoroughly investigated as a stopping
criterion.

For base 10, the trajectories of all integers < 196 reach a palindrome
after at most 24 steps of the algorithm, but in the trajectory of 196 a
palindrome has not been found, in spite of enormous computational
efforts (John Walker [1], Tim Irvin [2]). It is conjectured, but has not
been proved, that the trajectory of 196 never reaches a palindrome.

For base 2, the integer 10110 (22) plays a similar role to 196 for base 10.
However, John Walker reports, without giving a reference, that Ronald
Sprague has proved that the trajectory of 10110 never reaches a
palindrome. The present note establishes the following more general assertion
from which the statement about 22 follows as a special case.

Proposition:
If a trajectory of the 'Reverse and Add!' algorithm for base 2 contains
an integer a(k), b(k), c(k) or d(k), where k > 1 and
	a(k) = 3*(2^(2*k + 1) - 2^k),
	b(k) = 3*(2^(2*k + 1) + 2^k - 1),
	c(k) = 3*(2^(2*k + 2) - 2^k),
	d(k) = 3*(2^(2*k + 2) + 3*2^k - 1),
then this trajectory never reaches a palindrome.

Proof:
I.
In base 2 none of these integers is a palindrome. Integers a(k) and c(k)
begin with '1' and end with '0', integers b(k) and d(k) begin with '11'
and end with '01'.
II.
A positive integer n which has r digits in base 2, can be represented as
n = sum(v(i)*2^i, i = 0..r-1), where v(0),...,v(r-2) = 0 or 1, v(r-1) =
1.
If exactly s (0 <= s < r) of the least significant digits of n are zero,
then v(0) = ... = v(s-1) = 0, v(s) = 1, reverse(n) has r-s digits, and
reverse(n) 	= sum(v(i)*2^(r-1-i), i = 0..r-1) 
		= sum(v(i+s)*2^(r-1-i-s), i = 0..r-s-1)
		= sum(v(r-1-i)*2^i, i = 0..r-s-1).
a(k) = 3*(2^(2*k+1) - 2^k) has r = 2*k + 3 digits, where r >= 7 is odd.
a(k)	= 2^(2*k+2) + 2^(2*k+1) - 2^(k+1)  - 2^k
	= 2^(2*k+2) + sum(2^i, i = k+2..2*k) + 2^k
	= 2^(r-1) + sum(2^(r-3-i), i = 0..(r-7)/2) + 2^((r-3)/2).
Thus v(i) = 1 if and only if i = r-1, r-3, ... , (r+1)/2, (r-3)/2.
Applying now the formula for reverse(n), we get
reverse(a(k)) 	= 2^((r+1)/2) + sum(2^((r-3)/2-i), i = 0..(r-7)/2) + 2^0
		= 2^(k+2) + sum(2^(k-i), i = 0..k-2) + 2^0
		= 3*(2^(k + 1) - 1).
Similarly we get
reverse(b(k)) 	= 3*(2^(2*k + 1) - 2^(k + 1) + 1),
reverse(c(k)) 	= 3*(2^(k + 2) - 1),
reverse(d(k)) 	= 3*(2^(2*k + 2) - 5*2^k + 1).
III.
Now it can be easily verified, that
	a(k) + reverse(a(k)) = b(k),
	b(k) + reverse(b(k)) = c(k),
	c(k) + reverse(c(k)) = d(k),
	d(k) + reverse(d(k)) = a(k+1).
IV.
After an integer a(k), b(k), c(k) or d(k), where k > 1, the trajectory
consists of a cyclic repetition of integers of these forms. This
completes the proof.

V.
The beginning of the trajectory of 22 in base 2 is 10110, 100011,
1010100, Sequence A058042 (22, 35, 84 in base 10, A061561), and 84 = 3*(2^5 - 2^2) = a(2).


[1] J. Walker, <a
href="http://www.fourmilab.ch/documents/threeyears/threeyears.html">
Three Years Of Computing: Final Report On The Palindrome Quest</a>

[2] T. Irvin, <a
href="http://www.fourmilab.ch/documents/threeyears/two_months_more.html">
About Two Months of Computing, or An Addendum to Mr. Walker's Three
Years of Computing</a>