3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It could be also much less. It's not because you know a big prime number, that you know every prime number smaller than this first one. $\endgroup$ – Ievgeni Dec 10 '19 at 15:01
  • $\begingroup$ en.wikipedia.org/wiki/Sieve_of_Atkin $\endgroup$ – MyNinthAccount Dec 10 '19 at 16:24
5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Interesting that the sieve of Eratosthenes was used, instead of other more complicated sieves. $\endgroup$ – kodlu Dec 10 '19 at 17:48
  • $\begingroup$ Still a bit of room left in 64-bit ints. $\endgroup$ – Xonatron Oct 3 '20 at 23:55
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Looking over this, 10^13 an hour assumes a pretty high clock rate. My guess is that even 10^12 an hour per core with a wheel sieve is unrealistic. So it may actually take a few years with Summit to reach 10^20. Gerhard "Hasn't Started On The Tweets" Paseman, 2019.12.10. $\endgroup$ – Gerhard Paseman Dec 10 '19 at 17:09
  • $\begingroup$ I was reading an article the other day (quantamagazine.org/…) which mentions a very hard computational problem that was ultimately resolved by the so called Charity Engine (charityengine.com), coordinating participating computers around the world to create something very powerful. I would not be surprised if this can be utilised to reach $10^{22}$. $\endgroup$ – Vladimir Dotsenko Dec 10 '19 at 17:25
  • $\begingroup$ Indeed, if instead of 10000 cores we had ten billion cores, we could try having each core work on a trillion numbers and get it done in a few weeks. However, the Gates foundation may still need to underwrite the computation. Gerhard "With One Foundation Feeding Another" Paseman, 2019.12.10. $\endgroup$ – Gerhard Paseman Dec 10 '19 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.