mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2019-04-11, 13:14   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default Known primes

We know all primes, p such that p < 10: 2, 3, 5 7

We do not know all primes, r, such that r < 282,589,933-1

Therefore there is a prime, q, such that all primes less than q are known and proven, but there are primes greater than q not known.

What estimates can you make for the size of q?
lukerichards is offline   Reply With Quote
Old 2019-04-11, 13:51   #2
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24×239 Posts
Default

Quote:
Originally Posted by lukerichards View Post
We know all primes, p such that p < 10: 2, 3, 5 7

We do not know all primes, r, such that r < 282,589,933-1

Therefore there is a prime, q, such that all primes less than q are known and proven, but there are primes greater than q not known.

What estimates can you make for the size of q?
If memory serves, the number of primes less than 1027 is known, though I doubt they are all listed.

Pari-GP offers values of primelimit, the upper bound on the list of precomputed primes, of 232 or 264, according to whether you have a 32-bit or 64-bit machine.

I'm guessing the precomputation of all primes up to 264 might take a while, and the resulting vector of primes might use up a bit of RAM...
Dr Sardonicus is offline   Reply With Quote
Old 2019-04-11, 13:56   #3
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

967 Posts
Default

Quote:
Originally Posted by lukerichards View Post
We know all primes, p such that p < 10: 2, 3, 5 7

We do not know all primes, r, such that r < 282,589,933-1

Therefore there is a prime, q, such that all primes less than q are known and proven, but there are primes greater than q not known.

What estimates can you make for the size of q?
That is an interesting question. I believe it is a number "slightly" over 4*1018

Tomas Oliveira e Silva computed all prime numbers up to that limit exactly 7 years ago in April 2012. See http://sweet.ua.pt/tos/gaps.html

Perhaps –because it is relatively easy to do– someone else with the right equipment has computed 1015 over that limit.

Last fiddled with by rudy235 on 2019-04-11 at 14:07 Reason: spelling
rudy235 is offline   Reply With Quote
Old 2019-04-12, 14:31   #4
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by lukerichards View Post
What estimates can you make for the size of q?
I'm not sure this is a meaningful question. People don't actually use such lists of primes. What does it mean for a prime to be "known"? That someone has in principle run a probabilistic primality test on it, then thrown away the result?


For comparison, what do you think is the largest number such that someone has counted up to it, but no one has counted further?
uau is offline   Reply With Quote
Old 2019-04-12, 15:05   #5
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2,477 Posts
Default

Remeber that the universe has *only * 10^78 to 10^82 atoms.

Last fiddled with by firejuggler on 2019-04-12 at 15:06
firejuggler is online now   Reply With Quote
Old 2019-04-12, 18:21   #6
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by uau View Post
I'm not sure this is a meaningful question. People don't actually use such lists of primes. What does it mean for a prime to be "known"? That someone has in principle run a probabilistic primality test on it, then thrown away the result?


For comparison, what do you think is the largest number such that someone has counted up to it, but no one has counted further?
It wasn't supposed to be a meaningful question, that's why it was posted to "Fun Stuff 》Puzzles".
lukerichards is offline   Reply With Quote
Old 2019-04-12, 18:22   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

25×32 Posts
Default

Quote:
Originally Posted by firejuggler View Post
Remeber that the universe has *only * 10^78 to 10^82 atoms.
Struggling to identify the significance of this point, re the original question.
lukerichards is offline   Reply With Quote
Old 2019-04-12, 18:58   #8
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by firejuggler View Post
Remeber that the universe has *only * 10^78 to 10^82 atoms.
Quote:
Originally Posted by lukerichards View Post
Struggling to identify the significance of this point, re the original question.
It gives a hard upper bound on the number of "known" primes, depending on the representation used of course. Say an atom represents a bit and the primes are written in binary, then you can't know all the primes higher than ~ 7e81 because you run out of space.
CRGreathouse is offline   Reply With Quote
Old 2019-04-12, 19:21   #9
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

1001000002 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
It gives a hard upper bound on the number of "known" primes, depending on the representation used of course. Say an atom represents a bit and the primes are written in binary, then you can't know all the primes higher than ~ 7e81 because you run out of space.
Now that is a fascinating way to look at it.
lukerichards is offline   Reply With Quote
Old 2019-04-12, 20:22   #10
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

967 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
It gives a hard upper bound on the number of "known" primes, depending on the representation used of course. Say an atom represents a bit and the primes are written in binary, then you can't know all the primes higher than ~ 7e81 because you run out of space.
That is a really high number but the practical limit is way less than that.

I don't have any special predictive ability but I would say that the actual limit which is 4*1018 (which was reached on April 2012) can be at most be squared to 1.6*1037 and I don't expect anyone who is alive now will be alive if and when this happens.
rudy235 is offline   Reply With Quote
Old 2019-04-13, 15:02   #11
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

24×239 Posts
Default

Quote:
Originally Posted by rudy235 View Post
That is an interesting question. I believe it is a number "slightly" over 4*1018

Tomas Oliveira e Silva computed all prime numbers up to that limit exactly 7 years ago in April 2012. See http://sweet.ua.pt/tos/gaps.html

Perhaps –because it is relatively easy to do– someone else with the right equipment has computed 1015 over that limit.
Curiously, this is still less than 2^64, the maximum value for primelimit offered by Pari-GP for 64-bit machines.

This leads me to wonder -- what is the largest value for primelimit people actually use commonly? (The default is 500k.)
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 09:35.

Tue Dec 1 09:35:44 UTC 2020 up 82 days, 6:46, 1 user, load averages: 2.02, 1.76, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.