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

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 sum-of-digits 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 + [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 = 3a_n−1 + 1 with a₀ = 1. (This recurrence arises in relation to a certain shell sort routine.) 

PROPOSITION 3:  R₁₀(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² 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¹⁹⁹⁹, 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₁₀(a), because a is less than (2³)²⁰⁰⁰, 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 R₁₀(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₁₀(a) = 1.

Return to MathPages Main Menu