Self-Similar Reverse-Sum Sequences

For any positive integers N and B let R_B(N) denote the integer given by reversing the digits of N in the base B.  For example, R₁₀(2316) = 6132.  When the base B is understood, we can abbreviate the notation, and simply denote the digit reversal operation by a “prime” symbol, so the reversal of x is denoted by x′. (This operation is somewhat similar to logical negation, since two consecutive applications is the identity.) It's interesting that for some initial integers x₀ and bases B, the reverse-sum recurrence

produces a sequence that is quasi-periodic in the sense that self-similar strings recur at regular intervals. For example, in the base 4 beginning with the number 255 (decimal), the recurrence (1) leads to a palindrome-free sequence with the following six-step cycle

where [x]_n denotes a string of n consecutive x numerals.  Cycles of this kind can be constructed for any base equal to a power of 2, and for certain other bases. (See the note on Digit Reversal Sums Leading to Palindromes.)

In general we say a sequence of integers x_k, k = 0,1,2,... is "self-similar" with period p iff for each j, j = 0,1,.., p-1 every one of the numbers x_np+j is of the same form

where S_i(n) is a string of digits, possibly a function of n. For example, in the base four we saw above that every term x_6n+0 of a particular sequence was of the form

so S₁(n) = {22}, S₃(n) = {131}, S₅(n) = {12} for all n, whereas S₂(n) = {n 0s} and S₄(n) = {n 1s}. We could allow the S functions to be more complicated functions of n, but here we will focus on cases when S consists of either a constant string or else n repetitions of a single digit.

No one knows of any such self-similar "cycle" in the base 10, at least not for finite numbers. Of course, if we allow a doubly infinite strings of digits then we have the following self-similar sequences in the base 10:

Also, for finite strings of digits, there exist sequences that maintain identifiable patterns for many iterations.  For example, consider the base-10 reverse-sum sequence beginning with the integer 17509097067.  The first 16 values are

And so on. The three leading and trailing digits of this sequence repeat every 8 steps, and this pattern continues for nearly twelve complete cycles before it finally unravels. In fact, beginning with the decimal integer 175000047583067, the eight-step cycle of the outer digits persists for over twenty complete cycles (160 reverse-sum iterations) before unraveling. Naturally we can make a sequence that persists for an arbitrarily large number of cycles, merely by going to larger seed numbers. However, it isn't clear whether any sequence exists with infinitely many cycles. In all the known sequences the interior digits don't seem to exhibit any consistent pattern...except for the fact that they support the 8-step cycle of the outer digits for a finite number of cycles.

If this were a 6-step cycle instead of an 8-step cycle it might be possible to combine it with the 6-step doubly infinite pattern.  Even for the 8-step cycle of outer digits this come tantalizingly close to working, as illustrated by the sequence below

The pattern of borrows and carries necessary to support the inner digit cycle is nicely supported by the exterior digits, so [k*1] becomes [(k+3)*1] after six steps, but the pattern unravels by the time the outer digits start to repeat. There exist similarly persistent quasi-cycles with even more leading and trailing digits involved in the repeating portions of the strings. For example, consider the sequence of decimal numbers whose first 24 terms are shown below

The eight leading and eight trailing digits repeat every eight steps, and this persists for over 17 full cycles. However, the pattern does eventually unravel, so it is not a truly self-similar sequence.

To understand what is required to produce  a true self-similar sequence, it's instructive to examine the simplest example, which is the binary sequence of period 4 shown below

(For more binary examples, see the note on Binary Reverse-Sum Automata (602).) The next four terms are identical to these, except that the strings of five consecutive 0s or 1s are replaced by strings of six consecutive 0s or 1s. This pattern has the form shown below.

where ω represents B-1 in the base B, and the symbol [x] signifies a string of n consecutive x's. The letters a,b,c,... are fixed integers with specified numbers of digits in the base B. The parameters {a,c,f,d} each have j digits, the parameters {b,e} each have k digits, and the parameters {g,h} each have k+1 digits. In terms of these parameters the four consecutive elements of the sequence can be expressed as

Likewise the reversals of these elements can be expressed as

Now, the recurrence relation and self-similar property imply that, for all n, we have

Inserting the previous expressions and simplifying, we two separate sets of conditions, one for the “outer” variables {a,c,d,f} and one for the “inner” variables {b,e,g,h}. These conditions are summarized below:

It stands to reason that the conditions split into two independent parts, because the inner and outer strings are separated by an arbitrary number of 0s and ωs, and they don’t interact direction with each other, provided they are consistent with the pattern of 0s and ωs. Incidentally, the first and third left-hand equations imply the useful relation

For the binary (B = 2) four-step self-similar sequence noted above we have j = 2 and k = 4, because outer strings consists of two bits, and the first inner string consists of four bits. We also have the values

Substituting into the previous expressions confirms that these values satisfy the stated conditions. We could also search for other sets of numbers that satisfy those conditions. For any given base B and string lengths j and k, the preceding conditions can facilitate the search for suitable outer and inner strings. To search for an outer string, we can begin by selecting a value of  c, from which we get c′. Then we compute f′ from the relation f′ = B^j – c′, and this lets us compute f, so we can compute a′ from the relation a′ = f – 1 – c, and therefore we have a, so we can compute d from d = a + Bj – f′. From d we get d′, so we can determine the value of c from the final condition

If this value agrees with our initial choice of c, then these numbers satisfy the four conditions. If not, we need to select another value of c and try again.

Likewise we can search (independently) for a suitable inner string, by selecting a value of b, computing b′, and then e from the first of the four relations. This also gives e′, so we can use the second relation to compute g, and hence g′, and then use these values in the third relation to compute h and hence h′. We can then use the fourth relation

to compute the resulting value of b, and compare it with the original selected value. If they agree, we have a candidate solution. (The four conditions are necessary, but not strictly sufficient, because the number of digits in each variable might not be consistent with the four-step pattern, so this must be checked separately.)

It may seem that this approach is no better than brute-force searching, since we may need to try all of the j-digit numbers in the base B for the outer strings, and all the k-digit numbers for the inner strings. However, there is an interesting phenomenon that can sometimes be exploited to shorten the search. This is best illustrated by an example.

Suppose we wish to determine whether there is a suitable “inner” string (for this four-step pattern) of length j = 4 in the base B = 26. If we exhaustively check each of the 26⁴ = 456976 initial values of c, we find that indeed there is one solution, given by c = 443827. But notice that this value actually appears much earlier as one of the “output” values of c. The first trial value of c that leads to an integer output value is c = 2B² – 1 = 1351, and this leads to the output value 440911. This is also the next integer output value, which occurs with an input value of 3B² – B – 1 = 2001. The next input value of c that leads to an integer output value is 3B² – 1 = 2027, which leads to 443827. Thus by checking these output values we arrive at the solution almost immediately. (Only 38 distinct integer output values occur over the whole range of inputs values for k = 4 and B = 26.) For completeness, we list all the parameters for this solution.

In the base 26 the inner sequence of value is

Similarly, using the conditions for the outer strings with j = 8, we can find the solution

Combining these inner and outer solutions gives a complete self-similar reverse-sum sequence for the base 26

This is one of the “sporadic” sequences originally found by David Seal in 1996, although he didn’t indicate how he found it. The other known sporadic solutions, to bases other than powers of 2, are each six-step cycles, but they consist of inner and outer strings separated by alternating strings of 0s and (B–1)s, just like the examples in the base 2 and 26 discussed above.

It’s interesting that the outer strings are, in a sense, easier to find, because they are one-sided. Using the algorithm described above, we choose a value of c, which must begin with a 1, and we can compute a new value of c (the next one in numerical order that satisfies the divisibility requirement), which will also begin with a 1, but the next most significant digit will usually differ. We can take the two most significant digits of this number as our new trial value of c, and repeat the process. Once the first two digits have stabilized, we proceed to match the third most significant digit, and so on. In this way we can, with very few steps (on the order of the number of digits) either reach a limit cycle or else arrive at an outer-string solution. This method was used to find the following outer-string solutions for the simple four-step cycle.

Unfortunately, inner strings for this four-step cycle seem to be more rare. A suitable inner string solution for this pattern is known only for the bases 2 and 26. To understand more about the inner strings, recall the four basic relations

These equations involve eight unknowns, but of course the primed and unprimed variables are simply the reversals of each other. Furthermore, we know these are quasi-palindromic in the sense that the reflected digits differ from each other by at most 1 unit. This implies that the differences of the form x – x′ are just simple sums of unique powers of B, with coefficients –1, 0, or +1. Any particular choice of these coefficients gives a definite algebraic relation between each variable and and its reversal, so we can eliminate the primed variables from the above conditions, leaving just four equations in four unknowns and the base B. For any given base we can solve the system to determine if there is an integer solution.

For example, one possible set of reversal differences is

Solving these for the primed variables and substituting into the basic four conditions gives the system

The solution is

We can reduce the polynomials inside the brackets on the right by dividing through by the determinant 4B² + 7B + 4 of the coefficient matrix. This gives the remainders

Each if these must be divisible by 4B² + 7B + 4 in order to give integer values of b,e,g,h. (These are necessary but not sufficient conditions, because the determinant is not monic, so there may be unaccommodated factors of 4.) Since the denominator is a quadratic and these non-zero remainders are linear, it follows that there is only a small range of B values that could possibly satisfy the conditions. It’s easy to show that B = 26 is the only solution in positive integers. (The integer B = –4 also satisfies these four residual conditions, but doesn’t give integer values of b,e,g,h because of factors of four.)  Since every possible solution reduces to a set of conditions similar to this, the range of possible bases with a suitable inner string for this four-step cycle is limited. This is in contrast with the outer strings, for which there is no apparent upper limit.

To analytically determine B from these conditions, we could set

for some integer k. Solving for B gives two roots involving the square root of a quantity that must be a square in order to give an integer solution. This leads to the Diophantine condition

For another example, consider the possible set of reversal differences

Proceeding as before, we get the system

Again this leads to a set of four linear functions of B that must be divisible by the determinant 4B² + 7B + 4. The only positive integer B for which b,e,g,h, are integers is B = 2. The discriminant of the determinant is the square root of 15, so this number plays a prominent role in the relations involving any “inner string” solutions for this simple four-step cycle.

Return to MathPages Main Menu