San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA |
---|
Digit Sum Arithmetic for Any Base |
---|
This material is to extend results found for the division of decimal numbers by 9 and 11. Decimal numbers are simply polynomials in powers of ten. In the following are the results for numbers for any base B and division is by any digit D..
A cumulative weighted sum sequence for any number S=snBn+sn-1Bn-1+…+s0 is defined as follows:
where the weight h is (B−D).
The weighted sum of the digits of any number S is the value of wn, the final term of the sequence. When this process is repeated until the result is a single digit that single digit is known as the weighted digit sum. In what follows such an iterated summation is not involved.
The sequence {wi for i=0 to n} can be expressed as
And ultimately
For an example take the number 4321 to the base B=10 and let the digit D be 9. This means the weight h=10−9=1. The weighted sum sequence for 4321 is {4, 7, 9, 10] . Thus the weighted sum of its digits is 10. This means, as will be shown, that 4321−10=4311 is exactly divisible by 9=10-1. In fact 4311=9*479. The cumulative sums of the digits of 432 are 4, 7, 9. These form the quotient which should be 479 and it is.
Now consider D=8 and the number 102 to the base 10. The weight h=B−D=10-8=2. The weighted sum sequence is {1, 2·1+0=2, 2·2+2=6}. Thus 102−6=96 should be exactly divisible by 8, and it is; i.e., 96=12·8. Note that the first two terms of the weighted sum sequence are {1, 2) which form the quotient of 96 divided by 8 as 1·10+2=12.
Again consider D=8, B=10 and hence h=2, but let the number be 132. The weighted sum sequence is {1, 2·1+3=5, 2·5+2=12}. So the weighted digit sum is 12. Thus 132−12=120 should be exactly divisible by 8 and it is; i.e., 120=15·8. The first two terms of the sequence are 1 and 5 corresponding to the quotient of 15.
Now let the number 1326. The weighted sum sequence is {1, 2·1+3=5, 2·5+2=12, 2·12+6=30}. This means 1326−30=1296 should be exactly divisible by 8, and it is; i.e., 1296=162·8. The first three terms of the weighted sum sequence are {1, 5, 12}. The quotient 162 is equal to 1·10²+5·10+12, but it is appropriate to add the tens digit of 12 to the 5 to get the sequence {1, 6, 2}.
A polynomial over the integers is of the form
where the coefficients cj and the base k of the polynomial are integers and n is a nonnegative integer.
The largest power n in a polynomial is called its degree.
It is convenient to use the following notation for polynomials
where C stands for the sequence of coefficients {cn, cn-1, …, c1, c0}.
Let h be any integer except k. Note that
This is established by representing the two terms created from the LHS as
Thus the lemma:
Now consider the polynomial
and form P(C, h) and then [ P(C, k) − P(C, h)]
Note that (k−h) is a factor of each term of the above and therefore is a factor of the sum. Consequently
This means that
where Q is a polynomial in k and h. Hence
Thus P(C, h) is in the nature of a remainder upon the division of P(C, k) by (k−h).
In the notation established above for polynomials the weighted sum of the digits of a number with S as its sequence of coefficients is
The number N to the base B is P(S, B). Consider a digit D. Its weight h is (B−D). Therefore N−wn is P(S, B)−P(S, h) which is equal to Q(B−h)=QD.
Now consider the number U which can be constructed from the first (n-1) terms of the weighted digit sum sequence; i.e.,
Now consider the numbers UB and Uh.
On the other hand
Since wi = wi-1h + sn-i
This means that
Then UB−Uh is equal to
But w0=sn and wn=P(S, h). Thus
The remainder for N divided by D isthe same as the remainder of wn divided by D, Then quotient of N divided by D is the quorient of N−wn divided by D plus the quotient of wn divided by D.
These results are not limited to digits. For the extension to divisors which are any number see Digits of quotients for any divisors.
HOME PAGE OF Thayer Watkins |