SelfSimilar ReverseSum 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_{10}(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_{0} and bases B, the reversesum recurrence 

_{} 

produces a sequence that is quasiperiodic in the sense that selfsimilar strings recur at regular intervals. For example, in the base 4 beginning with the number 255 (decimal), the recurrence (1) leads to a palindromefree sequence with the following sixstep 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 "selfsimilar" with period p iff for each j, j = 0,1,.., p1 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_{1}(n) = {22}, S_{3}(n) = {131}, S_{5}(n) = {12} for all n, whereas S_{2}(n) = {n 0s} and S_{4}(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 selfsimilar "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 selfsimilar 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 base10 reversesum 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 eightstep cycle of the outer digits persists for over twenty complete cycles (160 reversesum 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 8step cycle of the outer digits for a finite number of cycles. 

If this were a 6step cycle instead of an 8step cycle it might be possible to combine it with the 6step doubly infinite pattern. Even for the 8step 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 quasicycles 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 selfsimilar sequence. 

To understand what is required to produce a true selfsimilar 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 ReverseSum 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 w represents B1 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 selfsimilar 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 ws, and they don’t interact direction with each other, provided they are consistent with the pattern of 0s and ws. Incidentally, the first and third lefthand equations imply the useful relation 

_{} 
For the binary (B = 2) fourstep selfsimilar 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 fourstep pattern, so this must be checked separately.) 

It may seem that this approach is no better than bruteforce searching, since we may need to try all of the jdigit numbers in the base B for the outer strings, and all the kdigit 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 fourstep pattern) of length j = 4 in the base B = 26. If we exhaustively check each of the 26^{4} = 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^{2} – 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^{2} – B – 1 = 2001. The next input value of c that leads to an integer output value is 3B^{2} – 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 selfsimilar reversesum 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 sixstep cycles, but they consist of inner and outer strings separated by alternating strings of 0s and (B1)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 onesided. 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 outerstring solution. This method was used to find the following outerstring solutions for the simple fourstep cycle. 

_{} 

Unfortunately, inner strings for this fourstep 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 quasipalindromic 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^{2} + 7B + 4 of the coefficient matrix. This gives the remainders 

_{} 

Each if these must be divisible by 4B^{2} + 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 nonzero 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 fourstep 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^{2} + 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 fourstep cycle. 
