List of primes

[Primeinator]

Does anyone know where I can find a list of prime numbers ranging from 13 to 15 digits? I have been googling and am yet unable to find a list...

[R.D. Silverman]

Originally Posted by Primeinator

Does anyone know where I can find a list of prime numbers ranging from 13 to 15 digits? I have been googling and am yet unable to find a list...

Nor will you. I suggest you estimate the amount of disk storage required
for such a list.

What might you want it for?

[cheesehead]

Primeinator,

Since you didn't specify a complete or exhaustive list, nor all primes in that range, you may wish to take a look at the "Prime Curios!: Index: Numbers with 11 to 16 digits" page at http://primes.utm.edu/curios/index.php?start=11&stop=16. Not all the numbers listed are prime, but many are, as the respective link targets will explain.

Example: http://primes.utm.edu/curios/page.ph...006003999.html explains that 1004006003999 is "A Scheherazade prime (inspired by R. Buckminster Fuller) of the form 1001^N + M, where in this case, N is 4 and M is - 2. [Croll]"

[dsouza123]

I have attached a simple small Windows text mode program
that will list primes to a file OR the screen,
starting at the number you enter and the next x numbers.

The issues of storage space and time to run should be considered.
If the number is big enough and you want millions of numbers,
it will take a while and files will be in megabytes.

Both the executable and source are included.

[jinydu]

Originally Posted by Primeinator

Does anyone know where I can find a list of prime numbers ranging from 13 to 15 digits? I have been googling and am yet unable to find a list...

Basically then, you want all the primes between 10^12 and 10^16. According to Mathworld:

Pi(10^12) = 37,607,912,018 (over 3.7 * 10^10)
Pi(10^16) = 279,238,341,033,925 (over 2.7 * 10^14)

That gives a total of 279,200,733,121,277 primes in the range you want (over 2.7 * 10^14). If each prime took up one byte of memory (obviously, a major underestimate), the whole list would still take over 279 Terabytes, far beyond current personal computer technology.

However, things are much easier if you're willing to settle for smaller primes. http://primes.utm.edu/nthprime/ gives you any of the first trillion primes.

[Primeinator]

Wow, thank you very much. Merci beaucoup! Now if only you could extend up to....say 10^13 primes lol. Too bad it would take too much memory.

[Peter Nelson]

I followed similar logic to yindyu but he beat me to post.

The request was for a list of primes from 13 to 15 digits (I assume inclusive) ie 13,14,15 decimal digits long.

Then Bob asked if you realised how many or how much space. I took this as an exercise.

The first number (13 digits long) is 1,000,000,000,000 ie 10^12
And the highest in your range (15 digits) 999,999,999,999,999 that is one less than 10^15.

Of course we know powers of 10 are not prime.

From Prime Number Theorem. We know the number of primes <= a number x approximates to x/log x.

This function is notated pi(x).

I used figures on this page to look up values of pi for different x values.

http://primes.utm.edu/howmany.shtml

Initially I looked up pi(1,000,000,000,000,000) and subtracted pi(1,000,000,000,000). The former is just one over 999,999,999,999,999 which has 15 digits in it.

There are therefore 29,844,570,422,669 - 37,607,912,018
= 29,806,962,510,651 prime numbers in the range you specified.

However they are not the same length: some are 13, some 14, some 15 digits long.

308,457,624,821 are 13 digits
2,858,876,213,963 are 14 digits
26,639,628,671,867 (the majority) are 15 digits

We could use a byte to store a digit on disk but that would be wasteful.
As the characters are all decimal digits 0-9 something like PKZIP could compress them up well. However we're not that clever, so lets assume a simple compression scheme. Four bits represent a 0-F hexadecimal character, so in an 8 bit byte we can store two digits of your prime.

Using this (not very efficient) scheme, the storage required is

221,814,323,098,080 bytes (I did this by summing storage at 13,14,15)
That's about 221,814,323 Megabytes, or 221,814 Gigabytes, or 222 Terabytes.

Storage systems of this size certainly do exist either as disk arrays or magnetic tape. I agree that most casual users may not have this space available.

So lets consider a better scheme:

We can use prefixing. Instead of listing all the digits we only list the ones that change between one prime and the next.
Or alternatively we write 1000000 then all the last 6 digits of numbers that start with 1000000. Next 1000001...... and so on. Either of these schemes are far more efficient, and do not rule out the possibility of also using the hex 2:1 scheme above.

I am believe that such a list (once calculated) with an appropriate storage scheme could be physically stored on a single modern hard drive.

I was aware of the lists jindyu pointed you at, but not of any specifically giving (some) 13 through 15 digit primes.

The best I can do is say it is certainly possible to generate them, and refer you to the page

http://primes.utm.edu/lists/small/small.html

The method used by Chris Caldwell to give these example numbers eg 10, 20, more digits long can be applied.

Chris describes his method and the tools used (eg UBASIC) but unfortunately doesn't give his source code. It is not that difficult to write though. He used random numbers for testing whereas you may just want to churn through the range sequentially.

Just out of interest, I think my numbers differ slightly from Jindyu, maybe because we differ in our interpretation of digits in your request.

[Primeinator]

Okay thanks. When I get some more time I'll have to look into that.

[ewmayer]

Regarding the storage issue, there's no need to store the primes explicitly - you simply store a table of differences between consecutive primes. Assuming the first prime of your list is odd, the differences will all be even, so you save another bit per entry by dividing the difference by 2. There are heuristic arguments that the difference between consecutive primes grows asymptotically as (ln x)^2, which is very slow. People have also computed the maximum differences between consecutive primes up to fairly large limits, so you should be able to find the largest gap for primes < 10^16 on the web and use it to determine how big your list word needs to be.

On second thought, we don't even need to worry about that - nearly all the prime gaps will be smallish (say less than 512), so a byte suffices to store any gap that is < 512 in gap/2 form. What do we do if a gap is larger? Well, since we know a gap must be > 0, we can reserve a zero-valued byte as a representing 512-plus-whatever-the-bext-byte-times-2-is. We can have as many zeros in a row as needed, i.e. can cover gaps of arbitrary size this way. Since gaps this large are very rare, that only trivially increases our storage. In short, one byte per prime (plus however many bytes are needed to explicitly store the starting prime and the occasional zero byte for a large gap) is perfectly adequate.

Addendum: I managed to dig up a table of the maximum gaps (which I adapted from Riesel's book) from an old Fortran p-1 code I had lying around. In the table below, read "case(x:y); diffh = z" as "for an upper bound between x and y, inclusively, the maximum gap/2 between consecutive primes <= y is z":

	  case(             4:             7);	diffh=1;
	  case(             8:            23);	diffh=2;
	  case(            24:            29);	diffh=3;
	  case(            30:            97);	diffh=4;
	  case(            98:           127);	diffh=7;
	  case(           128:           541);	diffh=9;
	  case(           542:           907);	diffh=10;
	  case(           908:          1151);	diffh=11;
	  case(          1152:          1361);	diffh=17;
	  case(          1362:          9587);	diffh=18;
	  case(          9588:         15727);	diffh=22;
	  case(         15728:         19661);	diffh=26;
	  case(         19662:         31469);	diffh=36;
	  case(         31470:        156007);	diffh=43;
	  case(        156008:        360749);	diffh=48;
	  case(        360750:        370373);	diffh=56;
	  case(        370374:        492227);	diffh=57;
	  case(        492228:       1349651);	diffh=59;
	  case(       1349652:       1357333);	diffh=66;
	  case(       1357334:       2101881);	diffh=74;
	  case(       2101882:       4652507);	diffh=77;
	  case(       4652508:      17051887);	diffh=90;
	  case(      17051888:      20831533);	diffh=105;
	  case(      20831534:      47326913);	diffh=110;
	  case(      47326914:     122164969);	diffh=111;
	  case(     122164970:     189695893);	diffh=117;
	  case(     189695894:     191913031);	diffh=124;
	  case(     191913032:     387096383);	diffh=125;
	  case(     387096384:     436273291);	diffh=141;
	  case(     436273292:    1294268779);	diffh=144;
	  case(    1294268780:    1453168433);	diffh=146;
	  case(    1453168434:    2300942869);	diffh=160;
	  case(    2300942870:    3842611109);	diffh=168;
	  case(    3842611110:    4302407713);	diffh=177;
	  case(    4302407714:   10726905041);	diffh=191;
	  case(   10726905042:   20678048681);	diffh=192;
	  case(   20678048682:   22367085353);	diffh=197;
	  case(   22367085354:   25056082543);	diffh=228;
	  case(   25056082544:   42652518807);	diffh=232;
	  case(   42652518808:  127976335139);	diffh=234;
	  case(  127976335140:  182226896713);	diffh=237;
	  case(  182226896714:  241160624629);	diffh=243;
	  case(  241160624630:  297501076289);	diffh=245;
	  case(  297501076290:  303371455741);	diffh=250;
	  case(  303371455742:  304599509051);	diffh=257;
	  case(  304599509052:  416608696337);	diffh=258;
	  case(  416608696338:  461690510543);	diffh=266;
	  case(  461690510544:  614487454057);	diffh=267;
	  case(  614487454058:  738832928467);	diffh=270;
	  case(  738832928468: 1346294311331);	diffh=291;
	  case( 1346294311332: 1408695494197);	diffh=294;
	  case( 1408695494198: 1968188557063);	diffh=301;
	  case( 1968188557064: 2614941711251);	diffh=326;
	  case( 2614941711252: 7177162612387);	diffh=337;
	  case( 7177162612388:13829048560417);	diffh=358;
	  case(13829048560418:19581334193189);	diffh=383;
	  case(19581334193190:42842283926129);	diffh=389;

[Uncwilly]

Originally Posted by ewmayer

Regarding the storage issue, there's no need to store the primes explicitly - you simply store a table of differences between consecutive primes.

Exactly, a prime server could store primes and when someone requested a list, send them the data and a little java app that would produce the list in-situ.

The say idea has been floated for those requesting M41 and M43 expansions. It would save loads of bandwidth for the server.

[grandpascorpion]

Since 6 is still the "jumping champion" in this range, I think you could save even more space by using a 4-bit solution.

Going this route, if you allow a prime gap of 8192 (4096*2 or (2^4)^3*2), you could store a difference of up to 26 (13*2) in only 4 bits.
This is still much more than the maximal prime gap in this range.

I have something in mind with the following space usage:
Gaps: 2-26 uses 4 bits
Gaps: 28-58 uses 8 bits
Gaps: 60-512 uses 12 bits
Gaps: 514-8092 uses 16 bits

I could be wrong here. I haven't crunched any numbers but on the surface, it looks like most of the time you would use half the space.