Talk:Chernick's Carmichael numbers: Difference between revisions
Content added Content deleted
m (Corrected typo in last edit.) |
(Optimization suggestion) |
||
Line 12: | 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) |
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) |