 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

164448 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 170148 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, 294 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! 11011111102 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, 02:55 #7 Peter Nelson   Oct 2004 232 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 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   2005-03-15, 03:02 #8 Primeinator   "Kyle" Feb 2005 Somewhere near M50..sshh! 37E16 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 26·181 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

17·541 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 50310 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   Thread Tools Show Printable Version Email this Page 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 00:01.

Thu Jan 21 00:01:30 UTC 2021 up 48 days, 20:12, 0 users, load averages: 2.24, 1.65, 1.58