Talk:Chernick's Carmichael numbers: Difference between revisions
Optimization suggestion
m (Corrected typo in last edit.) |
(Optimization suggestion) |
||
Line 12:
So my 16 billion wasn't even in the right ballpark and I estimate it would have taken my Go program about 8.5 days to find it, albeit on slow hardware. On a fast machine, using a faster compiler and GMP for the big integer stuff, you might be able to get this down to a few hours but it's probably best to remove it as an optional requirement as I see you've now done. Interesting task nonetheless so thanks for creating it. --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 15:03, 4 June 2019 (UTC)
::Or we could keep it. The task only gets interesting at 10. See beloe.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 09:34, 6 June 2019 (UTC)
==Optimizations==
The good news is no [[Casting out nines]]. The coefficients cₙ of the polynomials for 10 are:
<pre>
n cₙ
1 6
2 12
3 18
4 36
5 72
6 144
7 288
8 576
9 1152
10 2304
</pre>
For 10 m is divisible by 64, so the sequence begins 64 128 192 256 320 384 ... it is easy to see that this continues with 4 8 2 6 0 as the last digit. Which are the same last digits as cₙ. Consider the following table which shows the final digit of the number produced by the polynomial cₙ(m)+1:
<pre>
m 2 4 6 8
64 9 7 5 3
128 7 3 9 5
192 5 9 3 7
256 3 5 7 9
320 1 1 1 1
384
</pre>
Remembering that prime numbers cannot end in 5 from the above I deduce that if m is not divisible by 320 then at least 1 of the polynomials must have a non prime result. This reduces the work to be done by 80%. Using this I obtained an answer in 6h, 31min, 16,387 ms. This could easily be halved using pseudo-primes and validating the final result. There is an obvious multi-threading strategy which could cut the time to 1/number of threads. More interestingly programming wise is start prime testing for a given m from the 10th polynomial. Observe that if this is not prime then for m*2 the 9th polynomial can not be prime (it is the same number). Similarly for m*4 the 8th polynomial can not be prime ... down to m*128 for the 3rd polynomial and then m*384 for the first polynomial. If the 10th polynomial is prime but the Nth (down to the 3rd) is not then the same applies just shifted. Keeping track of the m that do not need to be tested should reduce the time significantly.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 09:34, 6 June 2019 (UTC)
| |||