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 , Tim Irvin ). 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).  J. Walker, Three Years Of Computing: Final Report On The Palindrome Quest  T. Irvin, About Two Months of Computing, or An Addendum to Mr. Walker's Three Years of Computing