Binary ReverseSum Automata 

For any positive integer n and base b, let R_{b}(n) denote the integer given by reversing the baseb digits of n. For example, R_{10}(7219) = 9127. For any initial integer n_{0} we can define a sequence recursively by 

_{} 

If the base b is understood from the context we can omit the subscript on R, and we can write the first few iterates as 

_{} 

and so on. Notice that if x and y have equal numbers of digits, and if there are no carries in the addition x+y then R(x+y) = R(x) + R(y). Thus without carries the function R is distributive for arguments with equal numbers of digits (or, equivalently, for polynomials of a fixed degree). If this was always the case, the iterates could be written as 

_{} 

and so on, where superscripts on R denote compositions. Of course, reversing the digits an even number of times is the same as not reversing them at all, so in this hypothetical case (i.e., with no carries, so that the reversal operations are all distributive) the iterates would reduce to 

_{} 

Thus, after the first iterate, all the subsequent iterates would be given by simply doubling the preceding term, which stands to reason, because beginning with n_{1} all the iterates are necessarily palindromic, and therefore reversal of the digits has no effect. The first iteration is special, because n_{0} can be an arbitrary positive integer, not necessarily palindromic. Hence under the hypothesis of no carries, only the first iteration is nontrivial. 

Admittedly the hypothesis of no carries seems to have little relevance to actual iterations of the reversesum operation for integers (as opposed to polynomials), but even without that restriction the underlying patterns in such iteration sequences exhibit a special affinity for powers of two, which is not surprising, since there is an obvious tendency toward palindromicity of the iterates, and the reversesum operation is simply doubling for palindromes. This underlying consonance with powers of two manifests itself in the existence of selfsimilar sequences of reversesum iterates in any base that is a power of 2, whereas such sequences do not exist for other bases (except for a small number of sporadic exceptions). 

In fact, for binary numbers (i.e., in the base b = 2), almost all initial values of n_{0} (in the range of small numbers) lead quickly to selfsimilar patterns. The first 40 terms in the sequence of reversesum iterates beginning with 1 is shown below. 


Naturally if we start with any of the numbers in this sequence we will get the same result, so this covers 1, 2, 3, 6, 9, 18, and so on. We also find that many of the sequences merge together, so there are only a relatively small number of distinct longterm sequences. In fact, every values of n_{0} less than 300 leads eventually to one of only twelve distinct sequences, exemplified by the sequences beginning with one of the values 

_{} 

Since each number consists of just 0s and 1s, it’s convenient to plot them at bits, with blue dots for 1s and black dots for 0s. The five figures below show the first hundred iterates of the reversesum operation, beginning with the numbers 1, 64, 70, 74, and 98 respectively. 


Each of these sequences converges on a wellbehaved selfsimilar cycle fairly quickly, as do the iterates beginning with 107, 259, 266, 275, and 298, as shown in the figures below. 


However, the sequence of reversesum iterates beginning with 16 requires a considerably larger number of iterations before reaching a regular pattern. This is shown in the figure below, which gives the first 250 iterates. 


There obviously are some important algebraic restrictions on the possible regular patterns. Superficially, we note that that the numbers tend to be antipalindromic. Some of the other restrictions can be seen by considering the regular pattern reached from an initial value of 1. The pattern consists of a 4step cycle exemplified by the 51st through 55th terms below. 


The terms of the sequence are related not only additively but also multiplicatively. Expressing each of the indicated segments algebraically, these five numbers can be written in the form 

_{} 

Consolidating powers of 2 and rearranging terms, these can also be written as 

_{} 

Hence the general expression for this regular pattern for iterations of binary reversesum sequences is 

_{} 

This proves that each term is a multiple of 3, and that the asymptotic rate of growth of the sequence is a factor of four on each fourstep cycle, so the longterm growth rate is the square root of 2 = 1.414…. per step. This is the square root of the growth rate that we would have expected if there were no carries, i.e., if the digital reversal operation was distributive over addition. For another example, the terms of the regular sequence reached from the number 64 have the fourstep algebraic form 

_{} 

It would be interesting to determine the algebraic forms for other regular patterns. It’s also interesting to note that the rate of growth during the chaotic phase of a sequence, or during the regular phase if there are several “imperfections” in the pattern (i.e., the nonuniform vertical “stripes” on the figures), tends to be noticeably greater than for a regular phase with only a single “imperfection”. 

Among the sequences we’ve examined so far, the sequence beginning with 16 remained chaotic for the most number of iterations, but it isn’t difficult to find sequences that remain chaotic even longer before reaching a regular pattern. One striking example is the sequence of reversesums beginning with the number 215302, which continues in a seemingly chaotic way for about five hundred iterations before finally arriving at a regular pattern, as shown in the figure below. 


Our discussion so far might suggest that every binary reversesum iteration sequence eventually reaches a regular pattern. However, there exist some sequences that are not known to ever reach a pattern. The smallest initial value leading to such a sequence is 271. The figure below shows the first 930 reversesum iterates beginning with 271, and it gives no sign of ever reaching a regular pattern. 


Although the reversesum sequences visually appear to be highly symmetrical, lefttoright, they actually exhibit antisymmetry in many of the lowerlevel details. The patterns bear a striking similarity to the seemingly chaotic patterns produced by simple linear cellular automata, although there are some fundamental differences, one of which is the fact that the rules for cellular automata are usually “local”, whereas the digital reversal function involved in these reversesum iterations is nonlocal, because each bit is influenced by bits from the previous iteration at opposite locations within the number. We can’t eliminate this nonlocality simply by folding over the numbers, because they must be refolded on each iteration. In this sense the reversesum iteration is similar to iterations of the nonlinear logistic equation, f(x) = kx(1x). In fact, if we regard the complementing operation 1 – x as analogous to digital reversal, and multiplication as analogous to addition, we see that the logistic map is indeed quite similar to the reversesum map. 

Naturally we can examine reversesum sequences in other bases, and we can identify the regular patterns for bases that are powers of 2, but for other bases the results appear to be rather uniformly scrambled, with less interesting patterns than are apparent in the binary sequences. 
