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

[–] 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!