Talk:Penta-power prime seeds
Just thought I'd mention, the Penta-power prime seeds must be odd as n^0+n+1 = n+2 can only be prime if n is odd if n >= 1. --Tigerofdarkness (talk) 08:33, 20 August 2022 (UTC)
- Right... and this is probably most efficiently implemented as a sequence of tests, one for each polynomial -- the smaller polynomials filter out so much that parallelism costs more than it would contribute. The stress here is primality testing on large numbers (the task requires testing 83 bit unsigned integers and the stretch goal requires testing 94 bit unsigned integers).
- Most (not all) tasks of this nature put primality testing of integers larger than 2^63 in the stretch goal. --Rdm (talk) 16:55, 20 August 2022 (UTC)
- Well, maybe it isn't the biggest optimisation of all time but any optimisation is surely useful - in order to achieve the stretch goal, numbers to over 10 million must be considered - even if the primality test almost instantly rejects the even numbers, that's still around 5 000 000 wasted tests. As it happens, it didn't make that much difference to the Algol 68 sample's run time (around 2% *) but it did make a difference. Perhaps you could see what checking odd and even numbers does to your runtime, when you have a solution ? --Tigerofdarkness (talk) 18:12, 20 August 2022 (UTC)
- * not a particularly scientific test - ran it once with odd and even and once with odd only --Tigerofdarkness (talk) 18:55, 20 August 2022 (UTC)
- Well, maybe it isn't the biggest optimisation of all time but any optimisation is surely useful - in order to achieve the stretch goal, numbers to over 10 million must be considered - even if the primality test almost instantly rejects the even numbers, that's still around 5 000 000 wasted tests. As it happens, it didn't make that much difference to the Algol 68 sample's run time (around 2% *) but it did make a difference. Perhaps you could see what checking odd and even numbers does to your runtime, when you have a solution ? --Tigerofdarkness (talk) 18:12, 20 August 2022 (UTC)
- Using get_prime() instead of n += 2 afforded me a 6-fold improvement. --Pete Lomax (talk) 20:31, 20 August 2022 (UTC)
- Quote:
the task requires testing 83 bit unsigned integers
- Good point. Added some verbiage to the task requirements for languages that can't easily do this. --Thundergnat (talk) 20:45, 20 August 2022 (UTC)
- That would be the first seven values of the sequence, for typical 64 bit fixed width arithmetic implementations. I'm not sure that that will satisfy many implementors if it's not made an explicit goal. --Rdm (talk) 23:47, 20 August 2022 (UTC)
- Apologies for missing the main thrust of your post earlier, Rdm - you are right and for 32 bit languages, you could find the first 3 and for 16 bit languages (PL/M, Action!, many BASICS, VTL-2, ...), the first 2. --Tigerofdarkness (talk) 10:20, 21 August 2022 (UTC)
- That would be the first seven values of the sequence, for typical 64 bit fixed width arithmetic implementations. I'm not sure that that will satisfy many implementors if it's not made an explicit goal. --Rdm (talk) 23:47, 20 August 2022 (UTC)
- Quote:
Hexa-power prime seeds - or not
I see there aren't any "Hexa-power prime seeds" other than 1, as there are no primes of the form n^5+n+1 where n > 1 according to A271209. --Tigerofdarkness (talk) 22:23, 20 August 2022 (UTC)
- Confess I googled it: n^5 + n + 1 is (n^2 + n + 1)(n^3 -n^2 + 1). --Tigerofdarkness (talk) 10:20, 21 August 2022 (UTC)