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=s_{n}B^{n}+s_{n-1}B^{n-1}+…+s_{0} 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 w_{n}, 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 {w_{i} 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 c_{j} 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 {c_{n}, c_{n-1}, …, c_{1}, c_{0}}.
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−w_{n} 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 w_{i} = w_{i-1}h + s_{n-i}
This means that
Then UB−Uh is equal to
But w_{0}=s_{n} and w_{n}=P(S, h). Thus
HOME PAGE OF Thayer Watkins |