I really hoped Matt Parker would have shown how to construct these divisibility rules, so I came up with my own method. Find prime P and natural number N such that P*N = a *10^b + c
The smaller a and c are, the better. b determines where you split the number.
Example: P=313 N=16 a=5 b=3 c=8
313*16=5008
313*16=5 *10^3 + 8
Now we can test for 223795=313*13*11*5
Split 223795 after the b:th number, 3rd in this case.
223795/10^3=223.795 decimal point separates the components A, B
Multiply the A=223 by c and subtract from the rest B=795 multiplied by a
B*a-A*c=
795*5-223*8=2191
Repeat if needed till you get to small enough number.
2191/10^3=2.191
191*5-2*8=939
which is easy to see that’s 3*313
Some bad combinations don’t reduce the starting number but they are at least always divisible by P. Those cases could be called Parker divisibility rules.
You can also see that when c is negative, A*c is added rather than subtracted, which explains why some method add or subtract like Vsauce vs James.
This is just a funny trick to simulate division and modulus by 10^b to get smaller number, while preserving the congruence.
It’s possible I made mistake somewhere, but was able to get correct answers with other few examples.
I wrote some terrible python code to search divisibility rules for a given number and it tests example product divisibility
Edit2: https://pastebin.com/Dkbq2chV Yet another revision, I got caught up in this project but I think it has enough features now. I added few command line options and details you can edit in the script.
I need to stop before I add more features. Here’s example output:
$ python ./findDivRules.py -h python ./findDivRules.py [Integer or "(Start,End)"] [Show example? (0,1)] [Example is divisible? (0,1)] [Parker style? (0,1)] [Rule count] [Rule index] Default command : python ./findDivRules.py 313 True False True 10 0 Range example : python ./findDivRules.py "[1,11]" 0 0 1 2 0 $ python ./findDivRules.py 313 True True True Found 3 rules for 313, showing first 10: P N a b c P*N 313 16 5 3 8 5008 313 32 1 4 16 10016 313 639 2 5 7 200007 313 has following divisibility rule using B*a-A*c Split the tested number into A and B after 3rd digit. Multiply A by 8 and multiply B by 5 Subtract A from B = B*5-A*8 Example: Using rules P=313 a=5 b=3 c=8 Testing 700807 divisibility by 313 A|B B*a-A*c Intermed 700|807 807*5-700*8 -1565 -2|435 435*5+2*8 2191 2|191 191*5-2*8 939 0|939 939*5+0*8 4695 Smallest iteration 939 = 313*3 700807 is divisible by 313I bet I could make your code 40,832,277,770% faster.
Funnily enough, I just sped up my own solution by 25000% without compromising anything.
https://pastebin.com/Dkbq2chV
I realized that multiplying the divisor P by its non-zero reciprocal digits, gets you near 10^n which are ideal numbers for the divisibility rules. Which should have been obvious since
n * (1/n) = 1, and cutting off the reciprocal results in approximation of 1, which can be scaled by 10^b.e.g. finding divisibility rules for 7
1/7=0.14285... 7*14=98 7*143=1001 7*1429=10003The first script was very naive brute force approach.
So instead of searching every combination of a, b and c, I can just check the near multiples of
P*reciprocal.The variables can be solved by
P*N = a*10^b + cwhen b is given and a is 1 to 97*1429=10003would expand toP*N=1*10^4+3It appears to always run in ~30 milliseconds regardless of the tested number, so this might be O(1) until some bottleneck kicks in. Though I have yet to verify the complexity as the quality of division rule depends on a,b and c ranges.
Edit: after some testing it’s some logarithmic complexity when P is bigger than 10^2000
P size, time seconds 10^3000, 3.11 10^4000, 6.43 10^5000, 11.27 10^6000, 17.69 10^7000, 26.31 10^8000, 37.09Plotting these gave about O(log(P)^2.5)
The bRange, math.gcd() and reciprocal scale with P digit count but rest of the calculations are O(1).
I have no idea why you would need 10^8000 divisibility rule designed hand calculations, but you can get one under a minute and this isn’t even multithreaded!