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

Return to MathPages Main Menu