San José State University |
---|
applet-magic.com Thayer Watkins Silicon Valley & Tornado Alley USA |
---|
Digit Sum Arithmetic for Any Base and Any Divisor |
---|
This material is to extend results found for the division of decimal numbers by 9 and 11. It was found that the cumulative sums of digits of a number generate the digits of the quotients of that number divided by 9 or 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 number as a divisor D.
A cumulative weighted sum sequence for any number S=s_{n}B^{n}+s_{n-1}B^{n-1}+…+s_{0} to be divided by any divisor D 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 divisor D be 9. This means the weight h=10−9=1. The weighted sum sequence is just the cumulative sums. For 4321 these cumulative sums are {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. In fact 4311=9*479. The cumulative sums of the first three digits from the left of 432 are 4, 7, 9. These indicate that the quotient which should be 479 and it is.
Similar properties prevail for 11=10+1 as do for 9=10−1 but involve more complex operations. The weight h for D=11 is (B-D)=10−11=−1. For example. if N=125 then the cumulative weighted sums are {1, (-1)1+2=1, (-1)1=5=4}. The weighted digit sum for 125 is 4. This means 125−4=121 should be exactly divisible by 11 and it is since 121=11·11. Note the first two cumulative sum are 1 and 1 so the quotient of 121 divided by 11 should be 1·10+1=11, 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.
The process for some numbers may involve a bit more than occurred in the above illustrations. The cumulative weighted sums may involve two-digit numbers or negative numbers. These are resolved by modifying the sums for higher order terms.
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 divisor 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 |