mersenneforum.org > Math Smallest untested number?
 Register FAQ Search Today's Posts Mark Forums Read

 2003-09-25, 20:00 #1 wirthi   Sep 2003 2 Posts Smallest untested number? Hi, is there a list somewhere on the Internet where one can look what numbers have already been tested if they are prime? I mean, it's obvious the numbers from 1 to a billion are tested (I guess much further ...). So, where's the borderline? Is there an (inofficial) "smallest number not yet tested" (or at least a region where that number could be). Gimps and similar projects are not testing all the numbers, and I guess nobody has done a sieve up to 2^13,466,917 so there should be a lot of untested regions in the numberspace ...
 2003-09-25, 20:09 #2 dsouza123     Sep 2002 2·331 Posts http://mersenne.org/primenet/summary.txt Shows what has been TF (trial factored) , LL (Lucas-Lehmer tested), DC ( double checked Lucas-Lehmer ). For mersenne primes. Updated every hour.
 2003-09-25, 21:13 #3 Prime95 P90 years forever!     Aug 2002 Yeehaw, FL 22·1,873 Posts See http://numbers.computation.free.fr/C...ixproject.html for the closest answer to your question. However, the question you ask is not tracked by anyone because if you know that all primes below x have been discovered, then it is trivial to find the next one larger than x and break the record.
2003-09-25, 22:17   #4
GP2

Sep 2003

2·5·7·37 Posts

Quote:
 Originally posted by Prime95 See http://numbers.computation.free.fr/C...ixproject.html for the closest answer to your question.

I'm not sure that that's actually the answer to his question.

Just like it's possible to determine whether a number is composite without actually knowing all of the factors, it turns out it's possible to calculate pi(x) (the number of primes <= x) without actually listing all of those primes.

Thus we know that pi(1021) = 21 127 269 486 018 731 928, without actually having a listing of all those 21 quintillion primes.
http://numbers.computation.free.fr/C...ingPrimes.html

 2003-09-26, 11:10 #5 wirthi   Sep 2003 2 Posts Hi, so if I understand that site you mentioned correctly, they tested all the numbers up to at least 4Γ10^22 if they are prime. That's more or less what I wanted to know, thank you! To clarify again: I wanted to know the smallest number not yet tested; that should be a little higher than 4x10^22 ... So, the numbers gimps is currently working on are by far higher than the smallest yet untested numbers. There could be millions of primes between 10^22 and M13466917. Thanks for the info, Christian
2003-09-26, 13:49   #6
GP2

Sep 2003

259010 Posts

Quote:
 Originally posted by GP2 Just like it's possible to determine whether a number is composite without actually knowing all of the factors,
Read: without actually knowing any of the factors

Last fiddled with by GP2 on 2003-09-26 at 13:50

2003-09-26, 14:21   #7
GP2

Sep 2003

2×5×7×37 Posts

Quote:
 Originally posted by wirthi so if I understand that site you mentioned correctly, they tested all the numbers up to at least 4Γ10^22 if they are prime. To clarify again: I wanted to know the smallest number not yet tested; that should be a little higher than 4x10^22 ...
No.

Quote:
 So, the numbers gimps is currently working on are by far higher than the smallest yet untested numbers. There could be millions of primes between 10^22 and M13466917. Thanks for the info, Christian

104,053,945 <= M13466917 < 104,053,946

So there's waaaaay more than mere "millions" of primes between 1022 and M13466917.

Nobody could possibly come up with a listing of all the primes from 1 to 1022... apart from the intractable computation it would take a billion hard drives just to store the data.

The point of the link was, it's possible to exactly calculate how many primes exist from 1 to 1022 without knowing what any of those primes are.

Apparently the Rensselaer Twin Primes Computing Effort sieved all primes up to 1016, so perhaps this is the closest answer to your question.

Last fiddled with by GP2 on 2003-09-26 at 14:21

2003-09-26, 14:27   #8
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2·3·13·137 Posts

Quote:
 Originally posted by wirthi Hi, so if I understand that site you mentioned correctly, they tested all the numbers up to at least 4Γ10^22 if they are prime. That's more or less what I wanted to know, thank you! To clarify again: I wanted to know the smallest number not yet tested; that should be a little higher than 4x10^22 ... So, the numbers gimps is currently working on are by far higher than the smallest yet untested numbers. There could be millions of primes between 10^22 and M13466917. Thanks for the info, Christian
No, I'm afraid you don't understand correctly.

All those 4x10^22 numbers were not examined individually and we do not know precisely which are prime and which are composite. All we know is how many primes exist below that limit.

It is possible to count things without examining the whole list. For instance, I can say that there are 500,000 even numbers in the range 1 through one million inclusive without having to go through all million numbers individually and classifying them as I go.

You are asking for something which noone can provide. It's unknown what the smallest number has not been tested. Even if somehow you discovered the answer, it would be a matter of milliseconds to test that one and so raise the limit, and then how would you know that someone else hasn't done the same thing between you learning of the limit and testing it?

My guess, and it is very much a guess, is that the smallest number not yet tested is much lower than your 4e22 and is more likely to be ten orders of magnitude smaller.

Paul

2003-09-26, 14:49   #9
roy1942

Aug 2002

47 Posts

Quote:
 Originally posted by GP2 So there's waaaaay more than mere "millions" of primes between 1022 and M13466917. Nobody could possibly come up with a listing of all the primes from 1 to 1022... apart from the intractable computation it would take a billion hard drives just to store the data.
...and it would take waaaaay more than a mere "billion" hard drives to store the data. (Either 10^9 amer. or 10^12 brit.)

2003-09-26, 15:16   #10
GP2

Sep 2003

259010 Posts

Quote:
 Originally posted by roy1942 ...and it would take waaaaay more than a mere "billion" hard drives to store the data. (Either 10^9 amer. or 10^12 brit.)
I used:
21 * 1018 = billion billion = quintillion primes less than 1021.

Assume 100 GB per hard drive, and assume that you store only the differences between consecutive primes and also use some compression scheme... I guess a billion hard drives was a conservative lower bound.

Last fiddled with by GP2 on 2003-09-26 at 15:21

 2003-10-05, 13:02 #11 nucleon     Mar 2003 Melbourne 20316 Posts I find this an interesting problem. If you were to allocate a byte to store each difference, you would need 7.8x10^9 100GB HDDs. This is to store all the primes up too 4 x 10^22. Pi (4x10^22) = 780 x 10^18 (approx) = 100x 10^9 x 7.8x10^9. Can this be done any better? Aside from the ultimate encoding - just saying the phrase 'all the primes <4x10^22', but that's one hell of a decode :) Is there any maths done on the distribution of prime differences? Is there any fuction to say given all the primes

 Similar Threads Thread Thread Starter Forum Replies Last Post rogue Conjectures 'R Us 26 2018-01-03 19:51 ONeil Information & Answers 4 2017-12-23 05:30 jasong Math 5 2007-05-29 13:30 ixfd64 Lounge 22 2006-02-01 17:06 Fusion_power Puzzles 8 2003-11-18 19:36

All times are UTC. The time now is 14:41.

Tue May 18 14:41:35 UTC 2021 up 40 days, 9:22, 1 user, load averages: 2.22, 1.96, 2.12