Sum-of-Digits Iterations Given a positive integer n, let SB(n) denote the sum of the base-B digits of n. If we apply the function SB iteratively we eventually arrive at a single-digit integer (in the range 0 to B−1) which we will denote by RB(n). We will say that n "reduces to" RB(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, RB(n) = n modulo B−1. PROOF:  The base-B representation of n is of the form Evaluating this expression modulo B−1, we can replace each B with 1, and we get Therefore, SB(n) = n modulo B−1, meaning that the sum-of-digits function is the identity function modulo B−1, and so are iterations of this function. Thus we have RB(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 + [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 aj, j=1,2,... defined by the recurrence an = 3an−1 + 1 with a0 = 1. (This recurrence arises in relation to a certain shell sort routine.) PROPOSITION 3:  R10(an) = 4 for all n greater than 0. PROOF:  By solving the linear recurrence it's easy to show that so clearly an+1 exceeds an by a multiple of 9, from which it follows that every an > 1 reduces to 4. For another application, consider the triangular numbers Tn defined as the sum of the first n positive integers. What is the period of the reduced values of Tn for the base B? We have Tn = 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 Tn in the base B will have a period of P if and only if Tn = Tn+P (mod B−1).  If B−1 is odd the division by 2 in Tn is unique, so we just need to verify the congruence Expanding both sides and cancelling the n2 terms gives Subtracting n from both sides gives which is clearly true. Therefore, if B is 'even' the sequence of reduced values of Tn 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 Tn is not unique modulo an even number. For example, with B=15, Tn is not congruent to Tn+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 Tn = Tn+28 (mod 14). In summary, the period of the reduced values of Tn 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 = 19991999, 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 R10(a), because a is less than (23)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 five-digit 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 two-digit 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 R10(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 = R10(a) = 1. Return to MathPages Main Menu