mersenneforum.org > Math List of primes
 Register FAQ Search Today's Posts Mark Forums Read

 2005-03-14, 22:52 #1 Primeinator     "Kyle" Feb 2005 Somewhere near M50..sshh! 2·3·149 Posts 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...
2005-03-14, 23:28   #2
R.D. Silverman

Nov 2003

723210 Posts

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?

 2005-03-14, 23:35 #3 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×599 Posts 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
2005-03-15, 01:30   #4
dsouza123

Sep 2002

2×331 Posts

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
 Primes.zip (9.7 KB, 277 views)

2005-03-15, 02:15   #5
jinydu

Dec 2003
Hopefully Near M48

2×3×293 Posts

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

 2005-03-15, 02:45 #6 Primeinator     "Kyle" Feb 2005 Somewhere near M50..sshh! 2·3·149 Posts 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.
 2005-03-15, 03:02 #8 Primeinator     "Kyle" Feb 2005 Somewhere near M50..sshh! 2×3×149 Posts Okay thanks. When I get some more time I'll have to look into that.
 2005-03-15, 20:03 #9 ewmayer ∂2ω=0     Sep 2002 República de California 2×3×11×149 Posts 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;
2005-03-15, 20:37   #10
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

212658 Posts

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.

 2005-03-15, 23:23 #11 grandpascorpion     Jan 2005 Transdniestr 503 Posts 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

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 0 2017-05-27 14:00 Lennart Twin Prime Search 58 2017-05-05 14:15 gd_barnes Sierpinski/Riesel Base 5 2 2008-07-01 04:09 rogue Sierpinski/Riesel Base 5 1 2007-02-23 00:35 hyh1048576 Software 5 2003-08-20 13:38

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

Sat Nov 28 08:50:32 UTC 2020 up 79 days, 6:01, 3 users, load averages: 1.64, 1.47, 1.51