Smallest untested number?

wirthi · 2003-09-25, 20:00

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 ...

dsouza123 · 2003-09-25, 20:09

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.

Prime95 · 2003-09-25, 21:13

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.

GP2 · 2003-09-25, 22:17

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(10²¹) = 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

wirthi · 2003-09-26, 11:10

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

GP2 · 2003-09-26, 13:49

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

GP2 · 2003-09-26, 14:21

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

10^4,053,945 <= M13466917 < 10^4,053,946

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

Nobody could possibly come up with a listing of all the primes from 1 to 10²²... 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 10²² without knowing what any of those primes are.

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

xilman · 2003-09-26, 14:27

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

roy1942 · 2003-09-26, 14:49

Quote:

Originally posted by GP2

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

Nobody could possibly come up with a listing of all the primes from 1 to 10²²... 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.)

GP2 · 2003-09-26, 15:16

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 * 10¹⁸ = billion billion = quintillion primes less than 10²¹.

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.

nucleon · 2003-10-05, 13:02

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

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 ...

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

2003-09-25, 20:09	#2
dsouza123 Sep 2002 296₁₆ 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 2×53×71 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-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-10-05, 13:02	#11
nucleon Mar 2003 Melbourne 5×103 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 <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