PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : General discussion : Largest prime where all smaller primes are known

Author Message
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 4,081
321 LLR Gold: Earned 500,000 credits (538,216)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Gold: Earned 500,000 credits (636,842)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (212,232)PPS LLR Gold: Earned 500,000 credits (883,715)PSP LLR Gold: Earned 500,000 credits (663,928)SoB LLR Silver: Earned 100,000 credits (217,346)SR5 LLR Gold: Earned 500,000 credits (531,229)SGS LLR Amethyst: Earned 1,000,000 credits (1,042,382)TRP LLR Gold: Earned 500,000 credits (561,429)Woodall LLR Gold: Earned 500,000 credits (781,741)321 Sieve Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)GFN Turquoise: Earned 5,000,000 credits (7,129,018)PSA Silver: Earned 100,000 credits (244,815)
Message 139572 - Posted: 10 Apr 2020 | 6:59:47 UTC
Last modified: 10 Apr 2020 | 7:18:16 UTC

To rephrase the title, up to what number have we found all primes?

Finding new large primes is nice, but I feel like this is just picking one prime here and there while the vast majority is still unknown. I know this is done because efficient primality tests exist for these number. How long would a desktop PC take to determine primality of a number with a magnitude of e.g. 10^9?

Using the x/(ln(x)-1) approximation, up to 10^9 there are about 50 million primes and up to 10^12 there are 38 billion primes. I would assume they are all known, but are they? :)

Profile dannyridel
Volunteer tester
Avatar
Send message
Joined: 3 Feb 19
Posts: 791
ID: 1097922
Credit: 3,783,734
RAC: 799
321 LLR Silver: Earned 100,000 credits (100,228)Cullen LLR Bronze: Earned 10,000 credits (36,962)ESP LLR Bronze: Earned 10,000 credits (36,309)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (22,645)PPS LLR Silver: Earned 100,000 credits (219,290)PSP LLR Silver: Earned 100,000 credits (100,559)SoB LLR Silver: Earned 100,000 credits (138,888)SR5 LLR Bronze: Earned 10,000 credits (64,280)SGS LLR Bronze: Earned 10,000 credits (35,164)TRP LLR Bronze: Earned 10,000 credits (67,784)Woodall LLR Bronze: Earned 10,000 credits (40,976)321 Sieve Gold: Earned 500,000 credits (506,814)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (30,033)PPS Sieve Gold: Earned 500,000 credits (825,895)AP 26/27 Silver: Earned 100,000 credits (141,505)GFN Gold: Earned 500,000 credits (859,368)PSA Silver: Earned 100,000 credits (373,034)
Message 139573 - Posted: 10 Apr 2020 | 7:16:13 UTC - in response to Message 139572.
Last modified: 10 Apr 2020 | 7:23:33 UTC

I think primegen tried this about a decade ago, and somehow that provable unattainable, so I don't think this would be a good idea.

Here's a link to PrimeGen's purpose.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com

GFN-14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1


Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 4,081
321 LLR Gold: Earned 500,000 credits (538,216)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Gold: Earned 500,000 credits (636,842)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (212,232)PPS LLR Gold: Earned 500,000 credits (883,715)PSP LLR Gold: Earned 500,000 credits (663,928)SoB LLR Silver: Earned 100,000 credits (217,346)SR5 LLR Gold: Earned 500,000 credits (531,229)SGS LLR Amethyst: Earned 1,000,000 credits (1,042,382)TRP LLR Gold: Earned 500,000 credits (561,429)Woodall LLR Gold: Earned 500,000 credits (781,741)321 Sieve Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)GFN Turquoise: Earned 5,000,000 credits (7,129,018)PSA Silver: Earned 100,000 credits (244,815)
Message 139574 - Posted: 10 Apr 2020 | 7:22:45 UTC
Last modified: 10 Apr 2020 | 7:24:12 UTC

Thanks, Primgen had some useful information. Apparently it took a Pentium II only 8 s to find all primes up to 10^9.

So I guess we have proceeded a lot farther than that.

Maybe there's not much use in finding all primes in a given range (on the other hand, are large primes useful?), but at least it could maybe tell us something about the distribution of primes and how closely they follow x(ln(x)? Is really no one working on this publicly?


edit: I found this site with all primes up to 10^12.

Profile dannyridel
Volunteer tester
Avatar
Send message
Joined: 3 Feb 19
Posts: 791
ID: 1097922
Credit: 3,783,734
RAC: 799
321 LLR Silver: Earned 100,000 credits (100,228)Cullen LLR Bronze: Earned 10,000 credits (36,962)ESP LLR Bronze: Earned 10,000 credits (36,309)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (22,645)PPS LLR Silver: Earned 100,000 credits (219,290)PSP LLR Silver: Earned 100,000 credits (100,559)SoB LLR Silver: Earned 100,000 credits (138,888)SR5 LLR Bronze: Earned 10,000 credits (64,280)SGS LLR Bronze: Earned 10,000 credits (35,164)TRP LLR Bronze: Earned 10,000 credits (67,784)Woodall LLR Bronze: Earned 10,000 credits (40,976)321 Sieve Gold: Earned 500,000 credits (506,814)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (30,033)PPS Sieve Gold: Earned 500,000 credits (825,895)AP 26/27 Silver: Earned 100,000 credits (141,505)GFN Gold: Earned 500,000 credits (859,368)PSA Silver: Earned 100,000 credits (373,034)
Message 139575 - Posted: 10 Apr 2020 | 7:25:11 UTC - in response to Message 139574.
Last modified: 10 Apr 2020 | 7:25:45 UTC

About this, I think every time you run an "Amicable Numbers" task, you have to calculate and store all primes below 10^11. That takes around a minute on Zen 1 mobile.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com

GFN-14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1


Profile dannyridel
Volunteer tester
Avatar
Send message
Joined: 3 Feb 19
Posts: 791
ID: 1097922
Credit: 3,783,734
RAC: 799
321 LLR Silver: Earned 100,000 credits (100,228)Cullen LLR Bronze: Earned 10,000 credits (36,962)ESP LLR Bronze: Earned 10,000 credits (36,309)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (22,645)PPS LLR Silver: Earned 100,000 credits (219,290)PSP LLR Silver: Earned 100,000 credits (100,559)SoB LLR Silver: Earned 100,000 credits (138,888)SR5 LLR Bronze: Earned 10,000 credits (64,280)SGS LLR Bronze: Earned 10,000 credits (35,164)TRP LLR Bronze: Earned 10,000 credits (67,784)Woodall LLR Bronze: Earned 10,000 credits (40,976)321 Sieve Gold: Earned 500,000 credits (506,814)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (30,033)PPS Sieve Gold: Earned 500,000 credits (825,895)AP 26/27 Silver: Earned 100,000 credits (141,505)GFN Gold: Earned 500,000 credits (859,368)PSA Silver: Earned 100,000 credits (373,034)
Message 139576 - Posted: 10 Apr 2020 | 7:35:42 UTC

And here is the answer to the question you were asking.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com

GFN-14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1


Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 4,081
321 LLR Gold: Earned 500,000 credits (538,216)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Gold: Earned 500,000 credits (636,842)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (212,232)PPS LLR Gold: Earned 500,000 credits (883,715)PSP LLR Gold: Earned 500,000 credits (663,928)SoB LLR Silver: Earned 100,000 credits (217,346)SR5 LLR Gold: Earned 500,000 credits (531,229)SGS LLR Amethyst: Earned 1,000,000 credits (1,042,382)TRP LLR Gold: Earned 500,000 credits (561,429)Woodall LLR Gold: Earned 500,000 credits (781,741)321 Sieve Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)GFN Turquoise: Earned 5,000,000 credits (7,129,018)PSA Silver: Earned 100,000 credits (244,815)
Message 139577 - Posted: 10 Apr 2020 | 7:40:12 UTC - in response to Message 139575.

I also found this article.

At the time of writing, whenever that was, 10^19 was at least taking up non-negligible time for computation.

What I don't get is this quote:

If we could give the smallest number n such that it is not known whether or not n is prime, then someone could check the next million primes in about a second of computer time (at most!)


Is this true? Wouldn't it depend on how large n is?

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 2,050
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Turquoise: Earned 5,000,000 credits (9,594,179)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (105,212)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Amethyst: Earned 1,000,000 credits (1,674,106)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 139582 - Posted: 10 Apr 2020 | 10:03:33 UTC

For such small primes, it really makes no sense to say which are "known" and which are not. Because it is extremely fast to test them, or find ranges of them by sieving.

For example, is the prime 123456789012419 known or not? Maybe someone with no interesting use for his disk space keeps a list of all primes up to this one? Otherwise, people have been sieving with this prime several times when sieving huge prime candidates of specific forms.

In any case, I can quickly find a prime like 123456789012419 again and again.

With the algorithms currently known, I can say more or less the same about much larger numbers. For example:

19274977647524045137176747261631187746108415626215325229208489430965464346826475939625734103100337620741385531281753006461219071364885762542087024324487417226115617524799488208682101513979132916210796814405170532841180456692645865935253160621642870250695588758055828781944984410800243831045972256652775296930985068201892919470097171237969667440025114747327301493864809266891116920128215548495811103587777501640289217786337247461123285453493305495576420471292946357150373935492857581578634258121054898834637310908005588813846155779237708147215620114352048942891758044711658313395487618062145141330152109201725524175045359043836313030302133790270048555942260587698367477221629047609315851989938692954145536698585567964765973246897264896248409655729427702349105577352059439358905597587630036194681573105140397557930800173501867184618943742721151333397726094420959544404008593525833938211500864129520164165197729018455605553138095373434396001812004389826823405857997063855903817737712419747133204592663989
is a prime number I just picked at random. It is probably not "known", but because I picked it and mentioned it here, is it "known" now? Nobody is going to remember this number, because you can always just pick another prime of this size any time you like.

/JeppeSN

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 4,081
321 LLR Gold: Earned 500,000 credits (538,216)Cullen LLR Amethyst: Earned 1,000,000 credits (1,169,946)ESP LLR Gold: Earned 500,000 credits (636,842)Generalized Cullen/Woodall LLR Silver: Earned 100,000 credits (212,232)PPS LLR Gold: Earned 500,000 credits (883,715)PSP LLR Gold: Earned 500,000 credits (663,928)SoB LLR Silver: Earned 100,000 credits (217,346)SR5 LLR Gold: Earned 500,000 credits (531,229)SGS LLR Amethyst: Earned 1,000,000 credits (1,042,382)TRP LLR Gold: Earned 500,000 credits (561,429)Woodall LLR Gold: Earned 500,000 credits (781,741)321 Sieve Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Amethyst: Earned 1,000,000 credits (1,045,010)AP 26/27 Ruby: Earned 2,000,000 credits (2,470,273)GFN Turquoise: Earned 5,000,000 credits (7,129,018)PSA Silver: Earned 100,000 credits (244,815)
Message 139600 - Posted: 11 Apr 2020 | 5:31:36 UTC - in response to Message 139582.
Last modified: 11 Apr 2020 | 5:37:55 UTC

So let's say a prime is "known" if it is either stored somewhere or can be found computationally within a conveniently short amount of time (whatever that is).

Most would agree that, prior to their discovery the current large primes have not been known according to that definition. And 1927497764752404... can be considered known even before you posted it.

There has to be a range of numbers in between where primes change from known to unknown. But it's an ever-moving range because of the ever-increasing computer power. So I see now that my question didn't really make sense the way I thought it would.


But I'm still not really satisfied with saying, it doesn't make sense to generate primes in order because apparently it does make sense to determine the primality of individual large numbers. And not just THE largest prime but also way smaller primes just because they can be constructed in a specific way.

We could just as well say, let's find all primes between the third and the second largest Germaine prime. The only difference from what we do is that it would take much (much much?) more time to find those and thus we keep picking specific one.


In conclusion, don't get me wrong, I enjoy doing this project. ;)

Profile dannyridel
Volunteer tester
Avatar
Send message
Joined: 3 Feb 19
Posts: 791
ID: 1097922
Credit: 3,783,734
RAC: 799
321 LLR Silver: Earned 100,000 credits (100,228)Cullen LLR Bronze: Earned 10,000 credits (36,962)ESP LLR Bronze: Earned 10,000 credits (36,309)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (22,645)PPS LLR Silver: Earned 100,000 credits (219,290)PSP LLR Silver: Earned 100,000 credits (100,559)SoB LLR Silver: Earned 100,000 credits (138,888)SR5 LLR Bronze: Earned 10,000 credits (64,280)SGS LLR Bronze: Earned 10,000 credits (35,164)TRP LLR Bronze: Earned 10,000 credits (67,784)Woodall LLR Bronze: Earned 10,000 credits (40,976)321 Sieve Gold: Earned 500,000 credits (506,814)Generalized Cullen/Woodall Sieve (suspended) Bronze: Earned 10,000 credits (30,033)PPS Sieve Gold: Earned 500,000 credits (825,895)AP 26/27 Silver: Earned 100,000 credits (141,505)GFN Gold: Earned 500,000 credits (859,368)PSA Silver: Earned 100,000 credits (373,034)
Message 139602 - Posted: 11 Apr 2020 | 6:27:24 UTC - in response to Message 139600.

Well in the end, it comes down to the ethics and definition of a "known" prime. So i think this discussion might need a closing.
____________
SHSID Electronics Group
SHSIDElectronicsGroup@outlook.com

GFN-14: 50103906^16384+1
Proth "SoB": 44243*2^440969+1


Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 2,050
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Turquoise: Earned 5,000,000 credits (9,594,179)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (105,212)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Amethyst: Earned 1,000,000 credits (1,674,106)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 139606 - Posted: 11 Apr 2020 | 8:04:05 UTC
Last modified: 11 Apr 2020 | 8:05:29 UTC

I should also say that the "form" of the prime matters when you decide if it is "trivial" or "a new find". The 1001-digit prime I posted before, I found with PARI/GP with nextprime(random(10^1000)+10^1000). In fact that one only returns a probable prime. This prime has no special form, so it actually takes a couple of minutes to verify it (I just used isprime from PARI/GP).

For primes with no special form, see for example The Top Twenty: Elliptic Curve Primality Proof. So a bit under 22,000 digits is enough to make it to Top 20, and 40,000 digits is enough to be #1.

On the other hand, for primes P where it is trivial to factor P-1 or P+1, we have much faster methods, and the threshold is higher. Already in November 1961, primes of special form with more than 1000 digits were found, namely the Mersenne primes 2^4253-1 and 2^4423-1, and today 1000-digit primes of a nice form are totally trivial. To see where a prime of a particular size would go in on the Top 5000, check the graph at How Fast are the Primes Growing? You can see that an "arbitrary" P-1 or P+1 prime that could just make the Top Fifty 20 years ago, is deemed uninteresting and "removed" from the list today (i.e. falls out of the Top 5000).

/JeppeSN

Post to thread

Message boards : General discussion : Largest prime where all smaller primes are known

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.07, 0.02, 0.00
Generated 28 Sep 2021 | 1:45:21 UTC