Talk:Chernick's Carmichael numbers: Difference between revisions
Optimization hints and news about a(11)
(Optimization suggestion) |
(Optimization hints and news about a(11)) |
||
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
:: In C++, using 64-bit integers, it's possible to compute '''a(10)''' in just '''~3.5 minutes''', with GMP for primality testing, '''preceded''' by trial division over odd primes up to p=23. It's very likely that one of the 10 factors ('''(6*m+1)''', '''(12*m+1)''', '''(18m+1)''', ...) is composite, having a small prime divisor '''<= p''', therefore we can simply skip it, without running a primality test on it. Another big optimization for '''n > 5''', noticed by Thundergnat (see the Perl 6 entry), and explained bellow by Nigel Galloway, is that '''m''' is also a multiple of '''5''', which makes the search 5 times faster. At the moment, the largest known term is '''a(11)''' (with '''m = 31023586121600''') and was discovered yesterday by Amiram Eldar. -- [[User:Trizen|Trizen]] ([[User talk:Trizen|talk]]) 14:27, 6 June 2019 (UTC)
==Optimizations==
The good news is no [[Casting out nines]]. The coefficients cₙ of the polynomials for 10 are:
| |||