Random Quote

Site Links

Welcome to p196.org!

Originally found at:

Self-Similar Reverse-Sum Sequences

For any positive integers N and B let R(N,B) denote the integer 
given by reversing the digits of N in the base B.  For example, 
R(2316,10)=6132.  It's interesting that for some initial integers 
x_0 and bases B, the recurrence

              x_(k+1)   =   x_k  +  R(x_k,B)                   (1)

produces a sequence that is "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

                          22 [n*0] 131 [n*3] 12
                      10 [(n+2)*3] 23 [(n+2)*0]
                         11 [n*0] 3222 [n*3] 01
                         22 [n*0] 2111 [n*3] 12
                      10 [(n+2)*3] 23 [(n+3)*0]
                  11 [(n+1)*0] 312 [(n+1)*3] 01
                  22 [(n+1)*0] 131 [(n+1)*3] 12

where [n*j] denotes a string of n consecutive j's.  Cycles of this 
kind have been constructed for any base equal to a power of 2, and 
for certain other bases. (See Dave Seal's results.)

However, apparently no one knows of any such "cycle" in the base 10.
Of course, if we allow a doubly infinite string of digits then we 
have the following self-similar sequences in the base 10

       period=1          period=2        period=6

      <..9999..>        <..3333..>      <..1111..>
      <..9999..>        <..6666..>      <..2222..>
      <..9999..>        <..3333..>      <..4444..>
      <..9999..>        <..6666..>      <..8888..>
      <..9999..>        <..3333..>      <..7777..>
      <..9999..>        <..6666..>      <..5555..>
      <..9999..>        <..3333..>      <..1111..>
         etc.              etc.            etc.

For finite strings of digits there are some sequences that maintain
their patterns for a long time.  For example, consider the base-10
reverse-sum sequence beginning with the integer 17509097067.  The first 
16 values are
                       175 09097 067
                       935 88187 638
                      177 266376 177
                      948 940038 948
                     179 8770088 797
                     977 7570867 768
                    184 55251625 547
                    930 07866881 028

                   175 026733751 067
                   935 184071371 638
                  177 1357241853 177
                  948 4938669384 948
                 179 79778337779 797
                 977 77551725577 768
                184 555104441155 547
                930 106248842711 028


The three leading and trailing digits of this sequence repeat every 
8 steps, and this pattern continues for nearly 12 complete cycles 
before it finally unravels.  However, 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.

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

                935 1111111111 638
               177 12222222223 177
               948 44444444444 948
              179 788888888889 797
              977 777777777777 768
             184 5555555555555 547
             930 1111111111111 028
            175 02222222222222 067
            935 24444444444442 638

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 6 steps.  Unfortunately the pattern unravels by the 
time the outer digits start to repeat.

QUESTION:  Does anyone know of any self-similar periodic reverse-sum
           sequences in base 10?

I suppose this sort of begs the question of what qualifies as a 
self-similar periodic sequence.  In general, the sequence of 
integers N_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 N_(np+j) is of the 
same form

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


so E1(n) = {22} for all n, whereas E2(n) = {n 0's}.  We could allow
the E functions to be more complicated functions of n, injstead of 
just determining the number of repetitions of a digit in a string, 
but I've never seen a self-similar sequence with any other kind of 

It's also interesting to observe the "palindromic quality" of the 
terms of sequences produced by iterating (1).  Notice that about 
half of the iterates are such that every digit is within 1 unit of 
its reflected counterpart.  Actually, the study of these palindromic 
effects are what has prompted most of the activity in this area, but 
I think the general question of self-similar periodic sequences is 
much more interesting.