Binary Reverse-Sum Automata

For any positive integer n and base b, let R_b(n) denote the integer given by reversing the base-b digits of n. For example, R₁₀(7219) = 9127. For any initial integer n₀ 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₁ all the iterates are necessarily palindromic, and therefore reversal of the digits has no effect. The first iteration is special, because n₀ can be an arbitrary positive integer, not necessarily palindromic. Hence under the hypothesis of no carries, only the first iteration is non-trivial.

Admittedly the hypothesis of no carries seems to have little relevance to actual iterations of the reverse-sum 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 reverse-sum operation is simply doubling for palindromes. This underlying consonance with powers of two manifests itself in the existence of self-similar sequences of reverse-sum 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₀ (in the range of small numbers) lead quickly to self-similar patterns. The first 40 terms in the sequence of reverse-sum 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 long-term sequences. In fact, every values of n₀ 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 reverse-sum operation, beginning with the numbers 1, 64, 70, 74, and 98 respectively.

Each of these sequences converges on a well-behaved self-similar 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 reverse-sum 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 anti-palindromic. 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 4-step 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 re-arranging terms, these can also be written as

Hence the general expression for this regular pattern for iterations of binary reverse-sum 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 four-step cycle, so the long-term 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 four-step 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 non-uniform 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 reverse-sums 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 reverse-sum 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 reverse-sum iterates beginning with 271, and it gives no sign of ever reaching a regular pattern.

Although the reverse-sum sequences visually appear to be highly symmetrical, left-to-right, they actually exhibit anti-symmetry in many of the lower-level 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 reverse-sum iterations is non-local, because each bit is influenced by bits from the previous iteration at opposite locations within the number. We can’t eliminate this non-locality simply by folding over the numbers, because they must be re-folded on each iteration. In this sense the reverse-sum iteration is similar to iterations of the non-linear logistic equation, f(x) = kx(1–x). 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 reverse-sum map.

Naturally we can examine reverse-sum 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.

Return to MathPages Main Menu