Largest known intervals of primes

Question

What is the (estimated) largest $X$ such that all primes less than $X$ have already been found? This question is different from the largest known primes as that might be much much bigger.

Answer 1

As a part of the efforts to verify the Goldbach conjecture up to $4\cdot 10^{18}$ all the primes up to this bound have been computed by Tomás Oliveira e Silva. It was computed using an efficient implementation of the sieve of Eratosthenes, which you can read about here. You can read more about the project as a whole here.

Answer 2

This question is difficult to answer as it stands. Primality tests (deterministic and randomized) work in reverse, given an input $n,$ there is a deterministic primality test due to Agarwal, Kayal, and Saxena which works with time complexity $O((\log n)^{12})$ [subsequently improved, I believe to $O((\log n)^6)$] to check primality.

So it is feasible to check primality of a very large primes. Other techniques such as sieve methods, can rule out primes and are used for factoring large integers.

But it is unlikely that we can know the largest interval $[1,N]$ for which all primes are known. We can estimate the computational complexity (and hence the feasibility) of determining all primes in some interval $[N-x,N]$ via primality tests, however.

For whatever it's worth, the computer algebra system Magma, available as an online calculator at http://magma.maths.usyd.edu.au/calc/ is able to answer a query returning all primes in an interval:

PrimesInInterval(10^17,10^17+10^3);

with the list

[ 100000000000000003, 100000000000000013, 100000000000000019, 100000000000000021, 100000000000000049, 100000000000000081, 100000000000000099, 100000000000000141, 100000000000000181, 100000000000000337, 100000000000000339, 100000000000000369, 100000000000000379, 100000000000000423, 100000000000000519, 100000000000000543, 100000000000000589, 100000000000000591, 100000000000000609, 100000000000000669, 100000000000000691, 100000000000000781, 100000000000000787, 100000000000000817, 100000000000000819, 100000000000000871, 100000000000000889 ]

but crashes if I query the interval of length $1001$ starting at $10^{18}$. It can actually even compute all primes in the interval $[10^{17}+10^{17}+10^8]$ though its output restriction means it can't display the list to an online [free] user. It crashes at the query for all the primes in $[10^{17}+10^{17}+10^9]$ due to memory restrictions for free users.

There are superior computational facilities at large industrial and government institutions that can do better, I am sure.

So, in principle, one can find all primes up to something like $10^{20}\approx 2^{66}$ if not much more. However, if one wanted to keep all of them in memory at the same time the memory required would be infeasibly large.

Answer 3

Some info to get a sense of scale.

I occasionally run sieving programs on a laptop for some of my investigations. Older laptop and non-optimized algorithm (for prime number generation, as I am looking at other things), I usually do much less than a billion ($10^9$) numbers an hour, which means it takes more than an hour to get to the first fifty million primes. There are faster systems out there; I had brief access to a cluster in Tennessee managed by OLCF, where I got up to over four billion within two hours (I need to check my notes, maybe it was ten billion), with slightly more optimal software. If I were just generating primes, I could probably get N up to $10^{11}$ in an hour, and people who have been working on this could probably get up to ten times that in an hour. Let's say they could do $10^{13}$ in an hour.

This cluster was a baby brother of Summit, which has over four thousand nodes and lots of processing cores and RAM. Suppose we could use a segmented sieve and divide the work among each core, both CPU and GPU, and cool things so that they could work at top speed. It is unrealistic but barely conceivable that they could achieve $N=10^{17}$, if the physicists and meteorologists could be persuaded to wait that hour while the system was monopolized for this computation.

Now assume you have the political pressure to monopolize the system for longer, and that the Gates foundation agrees to foot the electric and cooling bill. It would take over four days solid to reach the current known limit of about $10^{19}$, and a month and a half to reach $N=10^{20}$, using one of the most powerful supercomputer clusters on the planet solidly during that time, assuming it doesn't melt down.

And what do you have? Assuming a fantastic compression rate, you have several hundred terabytes of data recording the roughly $10^{17}$ or $10^{18}$ primes found above one billion, which you have at home. It would take longer to read through that than through all the tweets posted by everyone for the last few years, and would be only slightly more rewarding. So I believe we won't see $N=10^{22}$ for a few decades or until someone starts a computational GoFundMe.

So while the question is an interesting one academically, only machines will be able to understand and use the results. We mere mortals will have to depend on inferences drawn from what the computers tell us.

Gerhard "Sometimes Believes In His Laptop" Paseman, 2019.12.10.