mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-03-14, 22:52   #1
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M50..sshh!

11011111102 Posts
Default List of primes

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...
Primeinator is offline   Reply With Quote
Old 2005-03-14, 23:28   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Question

Quote:
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?
R.D. Silverman is offline   Reply With Quote
Old 2005-03-14, 23:35   #3
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

11100000101002 Posts
Default

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 1001N + M, where in this case, N is 4 and M is - 2. [Croll]"

Last fiddled with by cheesehead on 2005-03-14 at 23:45
cheesehead is offline   Reply With Quote
Old 2005-03-15, 01:30   #4
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

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.
Attached Files
File Type: zip Primes.zip (9.7 KB, 257 views)
dsouza123 is offline   Reply With Quote
Old 2005-03-15, 02:15   #5
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

110110111102 Posts
Default

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

Last fiddled with by jinydu on 2005-03-15 at 02:16
jinydu is offline   Reply With Quote
Old 2005-03-15, 02:45   #6
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M50..sshh!

2×3×149 Posts
Default

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.
Primeinator is offline   Reply With Quote
Old 2005-03-15, 02:55   #7
Peter Nelson
 
Peter Nelson's Avatar
 
Oct 2004

10000100012 Posts
Default

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.

Last fiddled with by Peter Nelson on 2005-03-15 at 03:00
Peter Nelson is offline   Reply With Quote
Old 2005-03-15, 03:02   #8
Primeinator
 
Primeinator's Avatar
 
"Kyle"
Feb 2005
Somewhere near M50..sshh!

89410 Posts
Default

Okay thanks. When I get some more time I'll have to look into that.
Primeinator is offline   Reply With Quote
Old 2005-03-15, 20:03   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

9,791 Posts
Default

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":

Code:
	  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;
ewmayer is offline   Reply With Quote
Old 2005-03-15, 20:37   #10
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

5·1,741 Posts
Default

Quote:
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.
Uncwilly is offline   Reply With Quote
Old 2005-03-15, 23:23   #11
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

503 Posts
Default

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.

Last fiddled with by grandpascorpion on 2005-03-15 at 23:29
grandpascorpion is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Here is a list of Mersenne Primes MattcAnderson MattcAnderson 0 2017-05-27 14:00
List of megabit primes found Lennart Twin Prime Search 58 2017-05-05 14:15
List of all base 5 primes? gd_barnes Sierpinski/Riesel Base 5 2 2008-07-01 04:09
Mistake in List of Primes rogue Sierpinski/Riesel Base 5 1 2007-02-23 00:35
Does Prime95 has a list of primes inside it??? hyh1048576 Software 5 2003-08-20 13:38

All times are UTC. The time now is 08:20.

Wed Oct 21 08:20:40 UTC 2020 up 41 days, 5:31, 0 users, load averages: 1.26, 1.33, 1.37

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