SumofDigits Iterations 

Given a positive integer n, let S_{B}(n) denote the sum of the baseB digits of n. If we apply the function S_{B} iteratively we eventually arrive at a singledigit 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 sumofdigits 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 baseB representation of n is of the form 



Evaluating this expression modulo B−1, we can replace each B with 1, and we get 



Therefore, S_{B}(n) = n modulo B−1, meaning that the sumofdigits function is the identity function modulo B−1, and so are iterations of this function. Thus we have R_{B}(n) = n (mod B−1), which was to be proven. 

The above proposition is 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 + [B1] 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} = 3a_{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 



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 if and only if 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 



Expanding both sides and cancelling the n^{2} terms gives 



Subtracting n from both sides gives 



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. The table below gives one complete cycle of reduced values of the triangular number for the bases from 2 to 16 (using hex for the digits): 



For a last example, consider the following riddle posed on the internet: Given a = 1999^{1999}, and suppose b is the sum of the digits of a, and c is the sum of the digits of b, and d is the sum of the digits of c, and e is the sum of the digits of d. What is the value of e? To answer this, we first deduce that the answer is the fully reduced value R_{10}(a), because a is less than (2^{3})^{2000}, which has 6001 digits, and the maximum possible sum of digits would occur if all the digits were 9s, so the maximum possible value of b is 54001, which is a fivedigit number, so the sum of digits must be less than 45 (which would occur if all five of the digits were 9s). Therefore, c is no greater than 45, which is a twodigit number, and the sum of its digits can be no greater than 18 (which would occur if both digits were 9s), so d is no greater than 18. It follows that the sum of the digits of d can be no greater than 9, so e is a single digit number, and hence it is the fully reduced value R_{10}(a). According to Proposition 1, this value equals a modulo 9. We see that 1999 = 1 (mod 9), and raising this to the power 1999 still leaves 1, so it follows that e = R_{10}(a) = 1. 
