"I
thought about looking at solving this problem, and split the
divisibility criteria into two varieties.
Case 1). Split the digits into groups of a specified size. Either
add all the groups, or alternatively add or subtract the groups.
Case 2). Take the last d digits. Multiply them by some small quantity,
and add them to the rest.
Case 3). Division by 2 or 5 is done merely by looking at the last digit,
since 2 and 5 are factors of the base 10.
Case 1) is actually a variant of case 2). (Make the small quantity
either +1 or -1).
So we look merely at case 2). Let our number be N, and let us
choose to take d digits from the end. Then N can be written as X*10^d +
Y, where Y is the last d digits of N. And we now wish to find an integer
k such that N is divisible by p if and only if X+kY is divisible by p.
We have the following logic, <=> denotes if and only if. p
is a prime, and is not 2 or 5 X+kY is divisible by p <=>
10^d(X+kY) is divisible by p <=> (X*10^d + Y) + (k*10^d-1)Y is
divisible by p
Hence, for our required division rule, given d, we must choose k
such that k*10^d-1 is divisible by p. Any choice of d will give us a
division rule. However the idea is to choose a value of d that is not
too large, and a value of k so that multiplication is not too difficult.
We search by value of d, and we will assume that it is easy to multiply
a d digit number by numbers 5 or less.
d=1
===
Division rules exist with multiplier k if 10k-1 is divisible by p. So we
attempt the k values from -5 to 5
k=-5: -51 has factors 3*17. We already know easier division rules
for these.
k=-4: -41 has factors 41. So here is a division rule for 41: subtract
four times the units from the rest.
k=-3: -31, again produces a division rule for 31: subtract three times
the units from the rest
k=-2: -21, gives the division rule you list for 7: subtract twice the
units from the rest
k=-1: -11, gives the division rule you list for 11.
k=1: 9, gives the familiar division rule you list for 3.
k=2: 19, gives a different rule than you list for 19: double the units,
add to the rest
k=3: 29, gives a rule for 29: multiply the units by 3, add to the rest
k=4: 39, gives the rule you list for 13: multiply
the units by 4, add to the rest.
k=5: 49, gives a rule for 7, but it is not so easy: multiply the units
by 5, add to the rest.
Before we continue with this search, we need to think, what
is an 'easy'
division rule? For instance, which rule is easier for 19?
- double the units, add to the rest, or
- add the hundreds to four times the rest
It appears the easiest rule is the rule that gives the smallest
value of k, however this may not always be true. For example, we can
always construct a rule for any prime p, with k=1. Since 10^(p-1)-1 is
divisible by p, a general division rule for p is take the last p-1
digits, and add to the rest. But this is not too helpful, since it may
only reduce our problem to p-1 digits.
So I started to search for division rules that work as follows.
Find a division rule with the smallest value of d, and for k values in
the range -5 to 5. Now we can reverse the process. Here is an algorithm
to find a suitable division rule for p.
1
Initialize R=1 and D=0
2 Calculate
X, such that 10X-1 is divisible by p.
3 In a loop:
3.1
increase D
3.2
multiply R by X
3.3 reduce
R modulo P to it's smallest absolute value (-P/2<R<P/2)
3.4 If R
is in the 'acceptable' range for multiplication (-5 to +5)
output the
rule - take the last D digits, multiply by R, add to the rest, and
exit the loop
If you prefer, you can change this algorithm so the test for R
tests against other values, for instance +-1, +-2, +-4 (if you do not
want to multiply by 3 in your rule).
Here is the list of division rules up to 100 generated using this
algorithm (it is very easy to go much higher)
13: take last 1 digits, multiply by 4, add to rest
17: take last 1 digits, multiply by 5, subtract from rest
19: take last 1 digits, multiply by 2, add to rest
23: take last 2 digits, multiply by 3, add to rest
29: take last 1 digits, multiply by 3, add to rest
31: take last 1 digits, multiply by 3, subtract from rest
37: take last 3 digits, multiply by 1, add to rest
41: take last 1 digits, multiply by 4, subtract from rest
43: take last 2 digits, multiply by 3, subtract from rest
47: take last 5 digits, multiply by 3, subtract from rest
53: take last 7 digits, multiply by 4, subtract from rest
59: take last 4 digits, multiply by 2, subtract from rest
61: take last 13 digits, multiply by 2, add to rest
67: take last 2 digits, multiply by 2, subtract from rest
71: take last 6 digits, multiply by 2, add to rest
73: take last 4 digits, multiply by 1, subtract from rest
79: take last 13 digits, multiply by 1, add to rest
83: take last 15 digits, multiply by 3, add to rest
89: take last 8 digits, multiply by 2, add to rest
97: take last 10 digits, multiply by 2, add to rest
Note some of them are not very easy to use, for instance, the rule
for 61 only reduces you to a 13
digit number. Any smaller reductions produce more difficult
multiplication needed. If you have an 8-digit calculator, a rule that
reduces things to 7 digits may be good enough.
Note there is an interesting feature of these rules. Any rule
generated may work for more than one number. For instance, take 59. The
rule is take the last four digits and multiply by -2. The rule works
since -2*10^4-1 = -20001 is divisible by 59. The other factors are 3
(for which we already have a division rule) and 113. So the rule for 59
works for 113, too!
So, there are now more questions:
1) Does anyone have any better rules
for 61, 79, 83, 89, and 97?
2) Is the method I chose (smallest number of digits to produce a
multiplier of 5 or less) the best algorithm?
3) are there any smarter methods (such as splitting into alternate
digits) that
produce better rules?
Finally, I revised the rules of the search a little. Suppose a
division rule for p can reduce the number to a value p^2 or less, and we
have division rules for smaller p. Then we can quickly factor the
remaining number. So I defined a *difficult* division rule as one that
would require the same number of digits (or more) than p^2 (and with the
same range of k as above).
Here are the hard division rules up to 1000:
47, 53, 59, 61, 71, 73, 79, 83, 89, 97, 103, 107, 109, 127, 139,
149, 151, 157, 163, 173, 179, 191, 193, 197, 211, 223, 227, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317,
331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 419, 421,
431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 503, 509, 521,
523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701,
709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 887, 907,
911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 "
