San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley U.S.A. |
---|
The Generalization of Digit Sum Arithmetic |
---|
The ordinary representation of number is to base 10. If the digits of that representation are summed and the result summed until a single digit is arrived at, that single digit is the digit sum of the number. A previous study showed that the digit sum of numbers to base ten is essentially the remainder of the number upon division by 9. The only difference is that the digit sum is zero only for the number zero, whereas the remainder after division by 9 is zero for any multiple of 9. For those cases the digit sum is 9 and 9 is equivalent to zero in the remainder arithmetic.
Let n_{k} be the representation of the integer n to the base k. This means that
Now digits means the digits from 0 to (k-1). For typgraphic convenience let the digit (k-1) be also denoted as h.
Let S(n) denote the sum of the digits of n; i.e., S = Σa_{i}. Then
Each of the terms (k^{q}-1) is a string of (k-1)'s, hhh…h, which is equal to (k-1)(111…1). Thus (k-1) is a factor and hence
The sum S(n) may be greater than (k-1). The same process can be applied to the representation of S to base k. Thus
where S_{1} is the sum of the digit of S(n). S_{1} also could be a number greater than (k-1); if so the procedure is applied iteratively until the single digit D is obtained. Thus
The digit D(n) is the digit sum of n. It is a number less than k which is the difference between the number n and a multiple of (k-1). It is thus the remainder for n upon division by (k-1).
The procedure could stop at the single digit of (k-1). In the remainder arithmetic (k-1) is equivalent to zero.
The above result may be expressed as
where n%(k-1) is the remainder after the division of n by (k-1). The symbol n_{k} denotes the number n expressed to base k.
The operations of addition modulo (k-1) have the property that for any two numbers n and m
For example, let k be 8 so (k-1) is 7. Note that the remainder arithmetic is modulo 7; i.e., with repect to 7, but the digit sums are with respect to base 8. Let n and m be 6 and 15, both to base 10. Thus 6%7=6 and 15%7=1. Six + one is seven and 7%7=0. This is the RHS of the above equation. However 6+15=21 and 21&7 is equal to 0. This is modulo 7 arithmetic.
Let D(q) be the digit sum of q. Thus for n and m
The digit sum arithmetic for the previous case is as follows. The digit sum of 6 is 6. However 15 to base 10 is equivalent to 17 to base 8. The digit sum of is 17 is 8, or equivalently 0. The sum of the digit sums is 14 to the base 10 and 16 to the base 8. The digit sum of 16 is 7. The sum of 6 and 15 to the base 10 is 21 to the base 10, but 21 to base 10 is 25 to the base 8. The digit sum of 25 is 7. Thus the RHS of the above equation matches the LHS. This is the digit sum arithmetic for the case.
Proof:
D(q_{k}) can be replaced by q%(k-1) for any q. Thus the LHS of the above equation is (n+m)%(k-1). The RHS is D(n%(k-1)+m%(k-1)), but n%(k-1)+m%(k-1) is the same as (n+m)%(k-1), which is the same as D((n+m)%(k-1)).
It is also true that
And likewise
Illustration: The numbers 6 and 15 to the base 10 will be used to illustrate the case for multiplication
(6%7)·(15%7) = 6·1 = 6. 6·15=90 and 90%7=6.
On the other hand
D(6)·D(17_{8}) = 6·8 = 48_{10} = 60_{8} and D(60_{8})=6. But 6·15_{10} = 90_{10} = 132_{8} and D(132)=6.
Proof:
Let n and m be expressed as a(k-1)+n%(k-1) and b(k-1)+b%(k-1). Then
The first three factors on the right are multiples of (k-1), therefore
In the equation D(n·m) = D([D(n)·D(m)]) the digit sums to base k can be replaced by their equivalents as remainders modulo (k-1). The result is
(To be continued.)
HOME PAGE OF applet-magic |
---|