Talk:Sisyphus sequence

Thirty billion primes

Regarding Pete's estimate that 30 000 000 000 primes with values up to around 570 000 000 000 would be needed for the Extreme stretch...
It occurred to me when I started this that the sieve needn't be held in memory. but the primes could be written to a file (probably several files) by another program and the Sysiphus sequence program just needs to read them one at a time. The values would easily fit in 8-byte integers - or 7-byte.
"All" that would be needed then would be a program to create the files of primes.
So how did Russ Cox do it ?
--Tigerofdarkness (talk) 21:07, 9 June 2023 (UTC)

The only other info I have (see here on Reddit) is that it only took him 2 hours! I'd imagine he'd be using C++ on his own machine as it's nothing to do with his work at google. This probably rules out using some sort of segmented sieve and, on the face of it, the algorithm for generating the sequence can't be parallelized - if you split up the numbers to be searched into chunks, the second chunk wouldn't know where to start in the prime sequence until the first chunk had been run.

The quickest way I know of to get from one prime to the next without using a sieve is to use GMP's mpz_nextprime function though the numbers here are 'small' by GMP's standards and there may be quicker ways which are optimized for 8 byte integers. Even so, it seems an extremely tall order to brute force this in only 2 hours and you may be right that he has a pre-built file or files of prime numbers to use for his OEIS work. --PureFox (talk) 08:13, 10 June 2023 (UTC)