mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-09-25, 20:00   #1
wirthi
 
Sep 2003

2 Posts
Default 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 ...
wirthi is offline   Reply With Quote
Old 2003-09-25, 20:09   #2
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2·331 Posts
Default

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.
dsouza123 is offline   Reply With Quote
Old 2003-09-25, 21:13   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

749110 Posts
Default

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.
Prime95 is offline   Reply With Quote
Old 2003-09-25, 22:17   #4
GP2
 
GP2's Avatar
 
Sep 2003

1010000111102 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2003-09-26, 11:10   #5
wirthi
 
Sep 2003

2 Posts
Default

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
wirthi is offline   Reply With Quote
Old 2003-09-26, 13:49   #6
GP2
 
GP2's Avatar
 
Sep 2003

2×5×7×37 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2003-09-26, 14:21   #7
GP2
 
GP2's Avatar
 
Sep 2003

2·5·7·37 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2003-09-26, 14:27   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×72×109 Posts
Default

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
xilman is offline   Reply With Quote
Old 2003-09-26, 14:49   #9
roy1942
 
Aug 2002

47 Posts
Default

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.)
roy1942 is offline   Reply With Quote
Old 2003-09-26, 15:16   #10
GP2
 
GP2's Avatar
 
Sep 2003

2×5×7×37 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2003-10-05, 13:02   #11
nucleon
 
nucleon's Avatar
 
Mar 2003
Melbourne

5·103 Posts
Default

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 <x, the max difference is approximately y?

Actually you'd need more than a byte to store the difference for all primes <4x10^22. Given that there are no odd differences except the difference between 2,3. You could store the primes with as a difference using a byte. That would give a max difference of 512.

But you'd stop at 304,599,508,537 as it's the first number with a gap of 514 to the next prime. (taken from [1])

So you could roughly on a single sided, single layer dvd store all primes (using a byte per difference) up to 10^11. Pi(10^11) = 4.1 x 10^9 (approx) (according to [2]) . A dvd stores around 4.7GB.

-- Craig


[1] = http://www.trnicely.net/gaps/gaplist.html
[2] = http://numbers.computation.free.fr/C...ingPrimes.html
nucleon is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Untested Sierp conjectures sorted by conjecture rogue Conjectures 'R Us 26 2018-01-03 19:51
I took a New assignment untested Prime Number manual testing &TF ONeil Information & Answers 4 2017-12-23 05:30
Could a Distributed Computing approach help find the smallest Brier number? jasong Math 5 2007-05-29 13:30
smallest number used in a mathematical proof? ixfd64 Lounge 22 2006-02-01 17:06
Can you find the smallest number? Fusion_power Puzzles 8 2003-11-18 19:36

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

Wed May 12 14:37:26 UTC 2021 up 34 days, 9:18, 0 users, load averages: 3.26, 3.56, 3.37

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.