Talk:Chernick's Carmichael numbers: Difference between revisions
Content added Content deleted
(Optimization hints and news about a(11)) |
(Thanks to Trizen and Nigel Galloway for providing some major optimizations.) |
||
| Line 15: | Line 15: | ||
:: 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) |
:: 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) |
||
:::Amazing speed-up as a result of these optimizations which, of course, are always obvious after some-one else has pointed them out :) |
|||
:::I've now added a second Go version (keeping the first version as the zkl entry is a translation of it). Even on my modest machine, this is now reaching a(10) in about 22 minutes so I'm very pleased. Think I'll leave a(11) to others though :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 10:07, 7 June 2019 (UTC) |
|||
==Optimizations== |
==Optimizations== |
||