Sum-of-Digits Iterations

The partitioning of data in the Shell Sort algorithm leads to the
recurrance relation a[n] = 3*a[n-1] + 1 with a[1]=1.  Kevin Marcus
noted that sum of the decimal digits of a[n] for n > 1 always equals
4, 13, 22, or 31, etc., and the sum of the digits of each of these
numbers is 4.

Let me try to describe what's going on here.  For all integers n>1
the value of a[n] has the property that if you sum it's (base 10) 
digits, and then sum the digits of that number, and so on until 
reaching a single digit number, you always arrive at 4.  This is 
a consequence of

PROPOSITION:  A positive integer n reduces to 4 iff n+9 reduces to 4.

PROOF:  The proposition is clearly true up to n=13.  Now suppose it is 
true for all integers < N, and let s(k) denote the sum of the digits 
of k.  If the least significant digit of N is 0, then s(N+9)=s(N)+9.  
Since s(N) < N we know that s(N) reduces to 4 iff s(N+9) also reduces 
to 4.  Therefore, N reduces to 4 iff N+9 reduces to 4.

If the least significant digit of N is greater than 0 and the next 
digit is less than 9, then s(N+9)=s(N) because the net effect is to 
decrease the least significant digit by 1 and increase the next digit 
by 1.  So again the proposition holds.

All that's left is the case where the least significant digit of N 
is greater than 0 and the next digit is 9.  In this case, the "carry" 
gets passed one digit further and the intervening 9 is set to 0.  If 
the next digit also happens to be 9, the carry gets passed again, 
and that 9 gets set to 0, and so on.  Thus, for each additional carry, 
the sum of digits is reduced by 9.  So we know that s(N+9) + 9k = s(N).   
Thus, s(N+9) and s(N) are linked by a sequence of "adding 9's", so 
they either both reduce to 4 or neither reduces to 4, which completes 
the proof.

Nowing turning back to the particular sequence in question, we know 
that
      a[n]  =   (3^n-1)/2

            =    1 + 3 + 3^2 + 3^3 + ... + 3^(n-1)

so clearly a[n+1] exceeds a[n] by a multiple of 9, from which it 
follows that every a[n] > 1 reduces to 4.

Of course, the above proposition on iterations of the sum-of-digits 
function immeidately generalizes to other bases and residues. In 
general we have

PROPOSITION:  Two numbers reduce to the same single digit under
              repeated summing of their digits in base B if and 
              only if they are congruent modulo B-1.  

which is useful in answering questions like the following:

On 3 Jan 1997 jrupe@advtech.uswest.com (Jason Rupe) wrote:
 Begin with the positive reals 1 2 3 4 5 ....  Then take the partial 
 sums from 1 to n for each n to yield 1 3 6 10 15 ...  Then, sum all 
 digits in each n so that, for example, 10 becomes 1+0=1, 15 becomes 
 1+5=6 and 148 would become 1+4+8=13 become 1+3=4, and such.  This 
 seems to result (should be easy to prove) in a recurring sequence 
 of 1 3 6 1 6 3 1 9 9.  

 In base 6, this also works with a recurring sequence of 1 3 1 5 5.  
 Notice that in both cases the period is base-1.  I half expected 
 this to also work with base 15, but it doesn`t seem to repeat, 
 unless the period is larger than 14, and base 14 doesn`t seem to 
 work either.  

 I would expect that this has already been discovered and studied.  
 I am interested in hearing about what is known about this 
 phenomenon.  Particularly, is there an easy way of predicting 
 the bases which exhibit the same properties as base 10 and base 
 6 described above, and are there any with finite recurring 
 sequences greater than base-1? 

The sum of the first n positive integers is s[n] = n(n+1)/2.  Also, 
we know that two numbers reduce to the same single digit (under 
repeated summing of their digits in base B) if and only if they 
are congruent modulo B-1.  Therefore, the sequence of reduced values 
of s[n] in the base B will have a period of T iff s[n] = s[n+T] 
(mod B-1).  If B-1 is odd the division by 2 in s[n] is unique, so 
we just need to verify the congruence

                  n(n+1)  =  (n+B-1)(n+B)   (mod B-1)

Expanding both sides and cancelling the n^2 terms gives

                 n  =  (2B-1)n + B(B-1)

Subtracting n from both sides gives

                   2(B-1)n + B(B-1)  =  0   (mod B-1)

which is clearly true.  Therefore, if B is 'even' the sequence of
reduces values of s[n] in base B will have a period of B-1.

For an 'odd' base the period is actually 2(B-1) instead of (B-1), 
because the division by 2 in the definition of s[n] is not unique 
modulo an even number.  For example, with B=15, s[n] is not 
congruent to s[n+14] (mod 14), they are only congruent (mod 7).  
We have to double the cycle to get the power of 2 back, so we 
have s[n] = s[n+28] (mod 14).

In summary, the period of the reduced values of s[n] in the base
B is B-1 if B is even and 2(B-1) if B is odd.  Here are the 
cycles for the bases from 2 to 16 (using hex for the digits):

  B
 ---
  2   1
  3   1 1 2 2
  4   1 3 3
  5   1 3 2 2 3 1 4 4
  6   1 3 1 5 5
  7   1 3 6 4 3 3 4 6 3 1 6 6
  8   1 3 6 3 1 7 7
  9   1 3 6 2 7 5 4 4 5 7 2 6 3 1 8 8
 10   1 3 6 1 6 3 1 9 9
 11   1 3 6 A 5 1 8 6 5 5 6 8 1 5 A 6 3 1 A A
 12   1 3 6 A 4 A 6 3 1 B B
 13   1 3 6 A 3 9 4 C 9 7 6 6 7 9 C 4 9 3 A 6 3 1 C C
 14   1 3 6 A 2 8 2 A 6 3 1 D D
 15   1 3 6 A 1 7 E 8 3 D A 8 7 7 8 A D 3 8 E 7 1 A 6 3 1 E E
 16   1 3 6 A F 6 D 6 F A 6 3 1 F F