20050314, 22:52  #1 
"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...

20050314, 23:28  #2  
Nov 2003
16444_{8} Posts 
Quote:
for such a list. What might you want it for? 

20050314, 23:35  #3 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 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 1001^{N} + M, where in this case, N is 4 and M is  2. [Croll]" Last fiddled with by cheesehead on 20050314 at 23:45 
20050315, 01:30  #4 
Sep 2002
1010010110_{2} 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. 
20050315, 02:15  #5  
Dec 2003
Hopefully Near M48
2·3·293 Posts 
Quote:
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 20050315 at 02:16 

20050315, 02:45  #6 
"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.

20050315, 02:55  #7 
Oct 2004
211_{16} Posts 
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 09 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 0F 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 20050315 at 03:00 
20050315, 03:02  #8 
"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.

20050315, 20:03  #9 
∂^{2}ω=0
Sep 2002
República de California
37×313 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 zerovalued byte as a representing 512pluswhateverthebextbytetimes2is. 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 p1 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; 
20050315, 20:37  #10  
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
7×13×101 Posts 
Quote:
The say idea has been floated for those requesting M41 and M43 expansions. It would save loads of bandwidth for the server. 

20050315, 23:23  #11 
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 4bit 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: 226 uses 4 bits Gaps: 2858 uses 8 bits Gaps: 60512 uses 12 bits Gaps: 5148092 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 20050315 at 23:29 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Here is a list of Mersenne Primes  MattcAnderson  MattcAnderson  0  20170527 14:00 
List of megabit primes found  Lennart  Twin Prime Search  58  20170505 14:15 
List of all base 5 primes?  gd_barnes  Sierpinski/Riesel Base 5  2  20080701 04:09 
Mistake in List of Primes  rogue  Sierpinski/Riesel Base 5  1  20070223 00:35 
Does Prime95 has a list of primes inside it???  hyh1048576  Software  5  20030820 13:38 