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
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
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 = 1. (This recurrence arises in relation to a certain shell sort
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):
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