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 nk be the representation of the integer n to the base k. This means that

n = aNkN + aN-1kN-1 + … + a1k1 + a0k0

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 = Σai. Then

n − S = aN(kN-1) + aN-1(kN-1-1) + … + a1(k-1)

Each of the terms (kq-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

n = (k-1)M + S(n)
or, equivalently
S(n) = n − (k-1)M

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

n = (k-1)M + (k-1)M1 + S1

where S1 is the sum of the digit of S(n). S1 also could be a number greater than (k-1); if so the procedure is applied iteratively until the single digit D is obtained. Thus

n = (k-1)ΣMi + D(n)
or, equivalently
D(n) = n − (k-1)ΣMi

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

n%(k-1) = D(nk)

where n%(k-1) is the remainder after the division of n by (k-1). The symbol nk denotes the number n expressed to base k.

Addition

The Arithmetic Modulo (k-1)

The operations of addition modulo (k-1) have the property that for any two numbers n and m

(n+m)%(k-1) = [(n%(k-1)) + m%(k-1)]%(k-1)

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

D((n+m)k) = D([D(nk)+D(mk)])

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(qk) 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)).

Multiplication

It is also true that

(n·m)%(k-1) = [(n%(k-1))·m%(k-1)]%(k-1)

And likewise

D(n·m) = D([D(n)·D(m)])

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(178) = 6·8 = 4810 = 608 and D(608)=6. But 6·1510 = 9010 = 1328 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

nm = ab(k-1) + a(k-1)(m%(k-1) + (n%(k-1))b(k-1) + (n%(k-1))(m%(k-1))

The first three factors on the right are multiples of (k-1), therefore

nm%(k-1) = [(n%(k-1))(m%(k-1))]%(k-1)

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

(n·m)%(k-1) = [(n%(k-1))·m%(k-1)]%(k-1)

(To be continued.)

HOME PAGE OF applet-magic