applet-magic.com
Thayer Watkins
Silicon Valley,
Tornado Alley
& BB Island
USA

The Sum of Digits for Multiples of Numbers

It is well known that the digits of multiples of nine sum to nine; i.e., 9→9, 18→1+8=9, 27→2+7=9, . . ., 99→9+9=18→1+8=9, 108→1+0+8=9, etc. Less well known is that the sum of digits of multiples of other numbers have simple patterns although not so simple as the case of nine. These are shown below:

NumberRepeating Cycle
of Sum of Digits
of Multiples
2{2,4,6,8,1,3,5,7,9}
3{3,6,9,3,6,9,3,6,9}
4{4,8,3,7,2,6,1,5,9}
5{5,1,6,2,7,3,8,4,9}
6{6,3,9,6,3,9,6,3,9}
7{7,5,3,1,8,6,4,2,9}
8{8,7,6,5,4,3,2,1,9}
9{9,9,9,9,9,9,9,9,9}
10{1,2,3,4,5,6,7,8,9}
11{2,4,6,8,1,3,5,7,9}
12{3,6,9,3,6,9,3,6,9}
13{4,8,3,7,2,6,1,5,9}

It is asserted that the sum of digits follows a repeating sequence of length 9. This is so because for any decimal representation x, the number 10*x (ten times x) will have the same sum of digits. Multiplication by the base number 10 simply moves the digits one place to the left and puts a zero in the units place. More generally,


DigitSum(10k*n) = DigitSum(n).
 

This operation, multiplication by the k-th power of 10, moves the digits k places to the left and places k zeroes on the right. The sum of digits is the same.

Less obviously adding a nine at any place in a decimal representation reduces the digit by one and adds one to the digit in the next higher place, and thus the sum of the digits is not altered. That is to say,


DigitSum(n+9*10k) = DigitSum(n).
 

Going back to the above table, what is immediately suggested by the information presented there is that the sequence for a multiple digit number m is the sequence for the sum of the digits of m, the digit sum of m. For example, the sequence for 12 is the same as the sequence for 1+2=3. Likewise the sequence for 13 is the same as the sequence for 1+3=4. This of course also holds true for 10.

The sequences for 3 and 6 are composed of the subsequences {3,6,9} and {6,3,9}, respectively. Thus the sequences for these digits have three copies of the subsequences of length 3. The sequence for 9 is nine copies of a subsequence of length 1. Note that {3,6,9}=3*{1,2,3} and that {6,3,9}=3*{2,1,3}. It is also worth noting that for all digits except 3, 6 and 9 the length of the sequence is nine and that for 3, 6 and 9 the lengths of their sequences, 3 and 1, are factors of 9.

The structures of the length 9 sequences are noteworthy. Here is a naive perception of the structure of the sequences. For 2 the sequence is the even digits in ascending order then the odd digits also in ascending order. For 4 the sequence is two generally descending sequences interleaved; i.e., 4,3,2,1,9 with 8,7,6,5 interleaved. For 5 the sequences is also two interleaved sequences but ascending rather than descending; i.e., 5,6,7,8,9 with 1,2,3,4 interleaved. For 7 the sequence is a descending sequence of the odd digits starting with 7 then the even digits in descending order with 9 the odd digit left out coming last. For 8 the sequence is a single descending sequence of digits starting with 8 and finishing with the digit 9 which was left out of the descending sequence. Later a more mathematical explanation of the structure of the sequences will be given.

The DigitSum Function

Let n be a number and let Dec10(n) be the decimal representation of n. Let DigitSum(z) be the ultimate sum of digits of a decimal representation z; i.e., if the sum of digits of a decimal representation is greater than nine then the sum of that number's digits is computed until a single digit is ultimately obtained.

This function, DigitSum( ), has several interesting properties; i.e.,

See Digit Sums for an analysis and proof of these propositions.

The proposition that DigitSum(x*y)=DigitSum(DigitSum(x)*y)) establishes that the sequences for the multiples of 12 and of 13 are the same as the sequences for 3 (1+2) and 4 (1+3), respectively.

Decimal Representation of Numbers

In order for the following to make sense one must stop thinking of a number in terms of its decimal representation and think of a number in terms of an appropriate number of tally marks so three would be (|||) and eleven (||||||||||||).

Consider how one obtains the decimal representation of a number. To get the last digit one divides the number by ten and takes the remainder as the last digit. That last digit is subtracted from the number and the result divided by ten. Then the decimal representation of that quotient is sought. The process is repeated and the next the last digit is obtained.

An alternate characterization of the process of finding the decimal representation of a number is that the k-th power digit for a whole number n is:


ck = (trunc[n/10k])%10
 

where trunc[] means the fractional part is thrown away and m%10 means the remainder after division by 10. In terms of the terminology from the programming language Pascal the formula is


ck(n) = (n div 10k) mod 10
 

The sum of the digits for a number n is then


Sum = Σk ck(n),
 

but this is not necessarily the digit sum for the number. The process has to be repeated iteratively on the sum of the digits.

The Explanation of the Patterns of the Sequences

Consider two digits, a and b. If their sum is less than ten then


DigitSum(a+b) = DigitSum(a)+DigitSum(b)
and hence
DigitSum(a+b) = DigitSum(DigitSum(a)+DigitSum(b)).
 

But, if the sum of a and b is ten or more then the decimal representation of their sum is a one in the ten's place and (a+b−10) in the unit's place. Thus


DigitSum(a+b) = 1 + (a+b−10) = a+b−(10−1) = a+b−9
 

For digits the DigitSum(a)=a and DigitSum(b)=b so


DigitSum(DigitSum(a)+DigitSum(b)) = 1 + (a+b−10).
 

Therefore for any two digits a and b


DigitSum(a+b) = DigitSum(DigitSum(a)+DigitSum(b)).
 

This applies as well to the digits in the k-th place. Thus the general proposition for any two decimal representations of numbers, x and y


DigitSum(a+b) = DigitSum(DigitSum(a)+DigitSum(b)).
 

For differences, if a and b are digits and a>b then


DigitSum(a−b) = DigitSum(DigitSum(a)−DigitSum(b)).
 

On the other hand if a<b then (a−b)=−(b−a) and, since DigitSum(−c) = DigitSum(c), it also holds that


DigitSum(a−b) = DigitSum(DigitSum(a)−DigitSum(b)).
 

Again this extends to the digits in any place in a decimal representation of a number.

For any decimal numbers x and y then


DigitSum(x±y) = DigitSum(DigitSum(x)±DigitSum(y)).
 

Since multiplication is simply repeated addition it also follows that


DigitSum(x*y) = DigitSum(DigitSum(x)*y)
DigitSum(x*y) = DigitSum(x*DigitSum(y))
and finally
DigitSum(x*y) = DigitSum(DigitSum(x)*DigitSum(y)).
 

It was previously noted that for any two digits whose sum is greater than ten,


DigitSum(a+b) = 1 + (a+b−10) = a+b−(10−1) = a+b−9
 

In general then for any decimal representation x


DigitSum(x) = Sumofdigits(x) − m*9
where m is such that DigitSum(x) is reduced to a single digit.
 

Another way of expressing this is that the DigitSum for a number n is simply the remainder after division by 9; i.e., DigitSum(n)=(n%9). DigitSum arithmetic is simply arithmetic modulo 9.

For comparison the multiplication table for modulo 9 arithmetic is:

<
Multiplication Table for Modulo 9 Arithmetic
000000000
012345678
024681357
036036036
048372615
051627384
063063063
075312642
08765432 1

If the 0's were replaced by 9's and the table rearranged so the first column becomes the last column and the first row becomes the last row the result would be identical to the table for the sequences of digit sums.

The Rearrangement of the
Multiplication Table for Modulo 9 Arithmetic
With 9 Substituted for 0
123456 789
246813 579
369369 369
483726 159
516273 849
639639 639
753126 429
8765432 19
999999999

Some Proofs

The proof of the property that the DigitSum of any multiple of nine is equal to nine starts with the obvious proposition


DigitSum(10*n) = DigitSum(n).
 

From this it follows from the proposition that DigitSum(x−y)=DigitSum(x)−DigitSum(y) that


DigitSum((10−1)*n) = 0
and thus
DigitSum(9*n) = 0
but in modulo 9 arithmetic
0 is the same as 9, so
DigitSum(9*n) = 9
 

The way to understand the sequence for 8 is that when 8 is added to any digit except 0 or 1 in any place the digit is reduced by 2 and one added to the digit of the next place. This results in a net decrease in the sum of digits of one. Thus when 8 is added to 8 the digit becomes 6, a reduction of 2, and 1 is added to the next higher digit, a net decrease in the sum of the digits of 1. Thus added 8 to 8 results in a sum of digits of 7. Adding 8 to 7 results in a sum of digits of 6, and so on down to adding 8 to 1 which gives 9. Even this fits into the rule in the sense that if 1 were reduce by 1 the result would be 0 which is equivalent to 9 modulo 9. Likewise adding 7 to a digit reduces it by 3 and adds 1 to the digit in the next place, a net reduction in the sum of digits of 2. Thus when 7 is added to 7 the sum of digits is reduced to 5. When 7 is added to 5 the sum of digits is reduced to 3. When 7 is added to 3 the sum of digits is reduced to 1. If 7 is added to 1 the result is 8, but that 8 could be consider as a reduction of 1 by 2 modulo 9. The addition of 7 to 8 results in a sum of digits of 6 and so on down to a sum of digits of 2. The addition of 7 to 2 results in a sum of digits of 9, but that 9 can be considered 0 modulo 9 and thus it is a reduction of 2.

Generalization to Other Number Bases

There is nothing special about 9; it is simply the number base ten less one. The digitsum sequences for multiples in the hexadecimal (base 16) number system is:

NumberRepeating Cycle
of Sum of Digits
of Multiples
2{2,4,6,8,a,c,e,1,3,5,7,9,b,d,f}
3{3,6,9,c,f,3,6,9,c,f,3,6,9,c,f}
4{4,8,c,1,5,9,d,2,6,a,e,3,7,b,f}
5{5,a,f,5,a,f,5,a,f,5,a,f,5,a,f}
6{6,c,3,9,f,6,c,3,9,f,6,c,3,9,f}
7{7,e,6,d,5,c,4,b,3,a,2,9,1,8,f}
8{8,1,9,2,a,3,b,4,c,5,d,6,e,7,f}
9{9,3,c,6,f,9,3,c,6,f,9,3,c,6,f}
a{a,5,f,a,5,f,a,5,f,a,5,f,a,5,f}
b{b,7,3,e,a,6,2,d,9,5,1,c,8,4,f}
c{c,9,6,3,f,c,9,6,3,f,c,9,6,3,f}
d{d,b,9,7,5,3,1,e,c,a,8,6,4,2,f}
e{e,d,c,b,a,9,8,7,6,5,4,3,2,1,f}
f{f,f,f,f,f,f,f,f,f,f,f,f,f,f,f,f}

In general, for numbers of base b the digit sums are equivalent to arithmetic modulo (b−1). The sequences which contain subsequences are the multiples of the factors of (b−1) other than unity. In the case of b=ten these factors are 3 and 9. Therefore there are subsequences for {3,6,9}. The lengths of the subsequences are (b−1) divided by the factors; i.e., in the case of b=ten 3 and 1.

For b=sixteen the factors are three, five and fifteen and so subsequences occur for {3,6,9,c,f,5,a} and the lengths of the subsequences are 3, 5 and 1.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins