Find a List of Primes up to 10^9 - No Generator Needed

[Dragonfall]

I need a list of primes up to at least 10^9 if possible. I don't want a program that will generate it as it will take too long. Does anyone know where on the net I can find a list that's already compiled? The largest I can find so far is 10^7.

The list doesn't have to be fancy, just the primes with returnspace or spaces between them will do.

EDIT: Actually, a good program that will generate primes and write them in a txt file will do too. I could write one, but I don't know any efficient primality tests for larger numbers.

 

[Pseudo Statistic]

http://primes.utm.edu/lists/small/millions/
Something like this maybe? (If this isn't enough for you, you have real issues :P)
Oh wait, just realized... I just linked you up to 10^8. :\

 

[Secret Squirrel]

from the prime number page:

Besides, downloading primes is a better use of bandwidth then much of the downloading done across the network.

 

[shmoe]

I would doubt anyone has such a list available to download. There are some 50,847,534 primes less than 10^9. Putting them in a text file would be enormous (for example the first 100,000 takes about 800KB before compression, 120KB zipped). Better would be to store them with 10^9 bits, 1 or 0 in the nth bit depending on whether n is prime or not. Unless you have an exceptionally slow computer and an exceptionally fast internet connection it will take more time to download 10^9 bits than it will to generate it from scratch (easily under a minute on any computer less than a few years old).

You wouldn't make a list by running a primality test on each number. The basic sieve of erathosthenes will be much faster and simpler to code. There are plenty of premade ones available (use google) if you don't want to write your own.

 

[Tide]

I am curious - what exactly would you do with such a list?

 

[Dragonfall]

I wanted to see if Benfrod's law applied to the primes for some reason. It doesn't.

 

[Tide]

I wanted to see if Benfrod's law applied to the primes for some reason. It doesn't.

Interestingly, Benford does work for Fibonacci numbers.

 

[Hurkyl]

I wanted to see if Benfrod's law applied to the primes for some reason. It doesn't.

Really? I find that odd... though I would find it plausible that you might have to get into big numbers to see it. (10^9 is not big)

If we assume small primes are a representative sample, is 50 million primes enough for a significant test?

 

[Dragonfall]

We tried for all primes up to 10 000 000 000. It's as even as it can get: approx. 11% each. Although it was quite funny when we first tried for up to the 1 000 000th PRIME and the 50 000 000th PRIME, where 50% of all primes started with 1. We were so startled that only later did I realize our mistake: sampling bias. If we analyse the primes from, say, 1 to 1 000 000, then again from 1 to 2 000 000, then OF COURSE there will be more primes starting with 1! So instead of going with the nth prime, we went with the nth number, and we gave all digits an equal opportunity to occur (stopping at 10^n), and it turns out that doesn't apply, at least for up to 10 bil.

There goes my fields medal :P

 

[Hurkyl]

So what you're saying is that Bedford's law is failing, because the distributions oscillate too much. Okay, I believe that!

 

[shmoe]

Benford's law applies to the primes in the same way it applies to the integers. e.g. the logarithmic density of integers starting with the digit y is log(1+1/y)/log(10). This means if S(n)=the sum of the recipricals of the integers starting with y that are less than n, then S(n)/log(n)->log(1+1/y)/log(10) as n->infinity.

For the primes if we set A(n) to be the sum of the recipricals of the primes less than n that begin with y, and B(n) to be the sum of the recipricals of the primes less than n, then we also have A(n)/B(n)->log(1+1/y)/log(10) as n->infinity. This is the relative logarithmic density of the primes beginning with y in the set of primes. This isn't too difficult to prove with a basic asymptotic for the sum of the recipricals of the primes.

This (logarithmic density view) is from Whitney in the 70's. There are other ways of looking at it though, like a straight asymptotic density (or rather an average, the asymptotic density doesn't exist).

 

[Dragonfall]

By "straight asymptotic density" do you mean the ratio (# of primes that start with k up to n)/(# of primes up to n)? If so, then that distribution seems to be completely uniform.

I'll try to read up on Whitney's works; I must confess I never heard of him/her. Thanks for the info.

 

[shmoe]

By "straight asymptotic density" do you mean the ratio (# of primes that start with k up to n)/(# of primes up to n)? If so, then that distribution seems to be completely uniform.

Yes that's what I meant by asypmtotic density, but I don't see how it could possibly converge. Let D(n) be the ratio you have above, with k=1, pi(n) the usual prime counting function. Then D(10^n)=D(2*10^(n-1))*pi(2*10^(n-1))/pi(10^n). The ratio pi(2*10^(n-1))/pi(10^n) will be close to 1/5 (by the prime number theorem), and hence D(10^n)<1/5 (as D is always <=1). On the other hand, D(2*10^n)>(pi(2*10^n)-pi(10^n))/pi(2*10^n)~1/2 (prime number theorem again). So it looks like D(n) will oscillate quite a lot and the asymptotic density is therefore undefined.

I'll try to read up on Whitney's works; I must confess I never heard of him/her. Thanks for the info.

Whitney just happened to be a paper on my hard drive: "Initial Digits For The Sequence of Primes", The American Mathematical Monthly, Vol. 79, (Feb, 1972), pp. 150-152. There will be more I'm sure.

 

[Dragonfall]

What I mean is that if you fix an initial number, then make increments of 10^n, then the distributions of primes with k starting digit looks to be more or less uniform. For instance, if you look at the first 1000, then 10000, then 100000, the proportions stay the same.

 

[shmoe]

That's not an asymptotic density then and is predicted by the prime number theorem. If n is 'large' you'd expect the number of primes in [y*10^n,(y+1)*10^n] to be 'about the same' for each y=1,..,9. These are long intervals relative to their height, you can make a more precise asymptotic statement.