Sum-of-Digits Iterations

Given a positive integer n, let s_B(n) denote the sum of the base-B
digits of n.  If we apply the function s_B iteratively we eventually
arrive at a single-digit integer (in the range 0 to B-1) which we will
denote by r_B(n).  We will say that n "reduces to" r_B(n) under iteration
of the sum-of-digits function.

PROPOSITION 1:  For any given base B, the positive integer n reduces to 
the residue of n modulo B-1.  In other words, r_B(n) = n modulo B-1.

PROOF:  The base-B representation of n is of the form

           n = d0 + d1 B + d2 B^2 + d3 B^3 + ...

Evaluating this expression modulo B-1, we can replace each B with 1, and
we get
           n = (d0 + d1 + d2 + d3 + ...) = s_B(n)   (mod B-1)

Therefore, the sum-of-digits function is the identity function modulo B,
and so are iterations of this function.  Thus we have r_B(n) = n (mod B-1),
which was to be proven.

Incidentally, the above proposition is obviously equivalent to the 
statement that

PROPOSITION 2: For a given base B, a positive integer n reduces to the 
residue j if and only if n+(B-1) reduces to j.

PROOF:  The proposition is clearly true up to n = B-1.  Now suppose it 
is true for all integers less than N.  If the least significant digit 
of N is 0, then s(N+[B-1]) = s(N) + [B-1].  Since s(N) is less than N,
we know s(N) reduces to j if and only if s(N+[B-1]) also reduces to j.
Therefore, N reduces to j if and only if N + [B-1] reduces to j.

If the least significant digit of N is greater than 0 and the next 
digit is less than B-1, then s(N+[B-1]) = 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 induction step holds.

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

For an application of Proposition 1, consider the sequence of integers
a[j], j=1,2,... defined by the recurrence a[n] = 3*a[n-1] + 1 with 
a[0] = 1.  (This recurrence arises in relation to a certain shell sort
routine.)  

PROPOSITION 3:  r_10(a[n]) = 4 for all n greater than 0.  

PROOF:  By solving the linear recurrence it's easy to show 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.


For another application, consider the triangular numbers T[n] defined
as the sum of the first n positive integers.  What is the period of
the reduced values of T[n] for the base B?  We have T[n] = n(n+1)/2,
and 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 T[n] in the base B will have a period of P iff T[n] = T[n+P] 
(mod B-1).  If B-1 is odd the division by 2 in T[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
reduced values of T[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 T[n] is not unique 
modulo an even number.  For example, with B=15, T[n] is not 
congruent to T[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 T[n] = T[n+28] (mod 14).

In summary, the period of the reduced values of T[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