Wikipedia:Reference desk/Archives/Mathematics/2020 August 18

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 18

holes in the primes

The search for big prime numbers concentrates on those of special form, like Mersenne numbers. But: what is the biggest natural number such that all smaller integers are known to be prime or composite? —Tamfang (talk) 01:49, 18 August 2020 (UTC)

According to some digging from this reddit post a few years ago, it seems to be in the neighborhood of 4×10¹⁸, but as pointed out there, any time a new upper limit is found, it's very computationally cheap to push it a little further, so there's really no fixed answer. I don't know if there have been any efforts since then or not. –Deacon Vorbis (carbon • videos) 02:04, 18 August 2020 (UTC)

Thanks for reading the question as I meant it! —Tamfang (talk) 16:51, 18 August 2020 (UTC)

Are you asking for the smallest N for which we can't in practice test primality with a computer? It would have to be quite large, because primality tests like the (probabilistic) Miller-Rabin test or the deterministic AKS primality test are "fast" in the sense of having runtime polynomial in the number of digits of N. See also this discussion. There are many Mersenne numbers and the like whose primality is unknown. It would be interesting to know the smallest mathematically significant number (such as a Mersenne number) whose primality is an open question. 2602:24A:DE47:BB20:50DE:F402:42A6:A17D (talk) 14:55, 18 August 2020 (UTC)

@Tamfang: AFAIK there is no such number - for each natural number X from 2 upwards, there is a natural number Y smaller than X, which is neither prime nor composite. And Y=1. Apart from this, however, each natural number except 1 is prime or composite, so again there is no the biggest number such that all numbers below it are prime or composite. --CiaPan (talk) 16:12, 18 August 2020 (UTC)

I'm not asking about numbers whose primality could be known. To put the question another way: what is the smallest odd number (above 1, har har) that has never been tested? Obviously we cannot know everything people do in the privacy of their computers. But there must be a number N such that the list of primes smaller than N is known to be complete. —Tamfang (talk) 16:51, 18 August 2020 (UTC)

I seriously doubt that that list is stored anywhere. There are roughly 93 quadrillion primes below Deacon Vorbis's 4x10¹⁸. If you store them as 64-bit integers, that's getting close to an exabyte, which is expensive, and the list isn't really good for anything. --Trovatore (talk) 17:35, 18 August 2020 (UTC)

According to the Mersenne primes page, M₁₅₇ is the first Mersenne number whose status is unknown. Your more general question is unanswerable. Perhaps 27368747340080916257 is actually the smallest number that has never been tested with a stringent primality test. Or perhaps some recluse in a remote cabin has proved this number prime with a revolutionary new method – but to avoid being put in the spotlight, they kept it a secret. I mean, how can we know for sure this is not the case?  --Lambiam 17:50, 18 August 2020 (UTC)

I'm confused, isn't M₁₅₇ known to be composite? (See [1] p 63.) If so then I'm not sure what you mean by "status is unknown". I didn't see it referenced on the primes page. --RDBury (talk) 11:07, 19 August 2020 (UTC)

I was looking at this page without being aware it was an historic document (from 1935!). Confusingly, the page itself has the same favicon (P..)as the Mersenne primes page and does not alert the reader to its non-contemporary status in any way or form.  --Lambiam 14:25, 19 August 2020 (UTC)

That explains it :) M₁₅₇ was shown to be composite in 1944; I don't know when it was fully factored though. --RDBury (talk) 19:40, 19 August 2020 (UTC)

According to Wolfram Alpha, the full factorisation of M₁₅₇ is 852133201 × 60726444167 × 1654058017289 × 2134387368610417. (I have not verified that this is correct...) AndrewWTaylor (talk) 13:37, 19 August 2020 (UTC)

PS the page mentioned in the next question ('Online ways to find factors of composite numbers') gives the same answer. AndrewWTaylor (talk) 13:44, 19 August 2020 (UTC)

Online ways to find factors of composite numbers

Here's a site that allows you to do such a thing:

http://www.alpertron.com/ECM.HTM

However, there are some numbers that it doesn't succeed well with. The defining criterion of a number it's hard to find a factor using this site is:

It's a composite number and no factors are found after 325 curves. (When the curves exceed 325 they take longer; this figure is exact; the 326th curve is the first curve that takes a long time.)

Any online site that's faster?? Georgia guy (talk) 16:22, 18 August 2020 (UTC)

You're better off spending a few hours writing your own program in C++ that implements the Montgomery curve method and which uses Montgomery modular multiplication. You then need to install Boost Multiprecision Library Count Iblis (talk) 12:34, 19 August 2020 (UTC).

If you mean other online services, I don't know of any, but there is tons of fancy factoring code out there, including for the number field sieve which I believe is still the asymptotically fastest known method. Is there a particular number you want to factor? Or a particular size of numbers? I've been out of touch with this field but I think these days, I think up to around 200 decimal digits is within reach of a hobbyist with some reasonable computer resources. 2602:24A:DE47:BB20:50DE:F402:42A6:A17D (talk) 09:53, 20 August 2020 (UTC)