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.
It 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!