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

[url]http://mersenne.org/primenet/summary.txt[/url]

Shows what has been TF (trial factored) , LL (Lucas-Lehmer tested), DC ( double checked Lucas-Lehmer ).

For mersenne primes.

Updated every hour.

See [url]http://numbers.computation.free.fr/Constants/Primes/Pix/pixproject.html[/url] 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.

[QUOTE][i]Originally posted by Prime95 [/i]
[B]See [url]http://numbers.computation.free.fr/Constants/Primes/Pix/pixproject.html[/url] for the closest answer to your question.
[/B][/QUOTE]


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[sup]21[/sup]) = 21 127 269 486 018 731 928, without actually having a listing of all those 21 quintillion primes.
[url]http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html[/url]

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

[QUOTE][i]Originally posted by GP2 [/i]
[B]Just like it's possible to determine whether a number is composite without actually knowing all of the factors, [/B][/QUOTE]

Read: without actually knowing [i]any[/i] of the factors

[QUOTE][i]Originally posted by wirthi [/i]
[B]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 ...
[/B][/QUOTE]

No.


[QUOTE][B]
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 [/B][/QUOTE]


10[sup]4,053,945[/sup] <= M13466917 < 10[sup]4,053,946[/sup]

So there's [i]waaaaay[/i] more than mere "millions" of primes between 10[sup]22[/sup] and M13466917.


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

The point of the [url=http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html]link[/url] was, it's possible to exactly calculate how many primes exist from 1 to 10[sup]22[/sup] [i]without knowing what any of those primes are[/i].


Apparently the [url=http://www.cs.rpi.edu/research/twinp/]Rensselaer Twin Primes Computing Effort[/url] sieved all primes up to 10[sup]16[/sup], so perhaps this is the closest answer to your question.

[QUOTE][i]Originally posted by wirthi [/i]
[B]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 [/B][/QUOTE]

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

[QUOTE][i]Originally posted by GP2 [/i]
[B]
So there's [i]waaaaay[/i] more than mere "millions" of primes between 10[sup]22[/sup] and M13466917.

Nobody could possibly come up with a listing of all the primes from 1 to 10[sup]22[/sup]... apart from the intractable computation it would take a billion hard drives just to store the data.
[/B][/QUOTE]

...and it would take [i]waaaaay[/i] more than a mere "billion" hard drives to store the data. (Either 10^9 amer. or 10^12 brit.)

[QUOTE][i]Originally posted by roy1942 [/i]
[B]...and it would take [i]waaaaay[/i] more than a mere "billion" hard drives to store the data. (Either 10^9 amer. or 10^12 brit.) [/B][/QUOTE]

I used:
21 * 10[sup]18[/sup] = billion billion = quintillion primes less than 10[sup]21[/sup].

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.

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] = [url]http://www.trnicely.net/gaps/gaplist.html[/url]
[2] = [url]http://numbers.computation.free.fr/Constants/Primes/countingPrimes.html[/url]