math

828 readers

1 users here now

General community for all things mathematics on @lemmy.world

Submit link and text posts about anything at all related to mathematics.

Questions about mathematical topics are allowed, but NO HOMEWORK HELP. Communities for general math and homework help should be firmly delineated just as they were on reddit.

founded 2 years ago

MODERATORS

mrh

I generalized constructing divisibility rules by any prime (www.youtube.com)

submitted 3 weeks ago* (last edited 3 weeks ago) by Kaelygon to c/math

4 comments fedilink hide all child comments

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.

you are viewing a single comment's thread
view the rest of the comments

[–] Kaelygon 3 points 3 weeks ago* (last edited 3 weeks ago) (1 children)

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 313

[–] CrayonRosary 3 points 3 weeks ago (1 children)

I bet I could make your code 40,832,277,770% faster.

[–] Kaelygon 1 points 3 weeks ago (1 children)

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=10003

The 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 + c when b is given and a is 1 to 9
7*1429=10003 would expand to P*N=1*10^4+3

[–] Kaelygon 1 points 3 weeks ago* (last edited 3 weeks ago)

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.09

Plotting 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!