20110415, 03:40  #1 
Aug 2006
3×1,993 Posts 
Extrapolation: How long until the minimum megaprime?
No doubt many are thinking of M6972593, but I mean the smallest prime with one million digits. How difficult would this be to find?
The straightforward approach would be to sieve a small number (few million) candidates to a high enough level (at least 10^14?) to remove most of the composites, and then ~10,000 pseudoprimality tests (requiring effort similar to a standard LL test  smaller numbers but not as optimized, presumably). This would be too hard to be practical today without a distributed effort, it seems, but when might it be reasonable? I would also be interested in guesses for how much longer until this number could be *proved* to be the first such prime. Unlike finding it, proving its primality might not be possible in my lifetime, barring breakthroughs in algorithms (not particularly unlikely, I suppose). 
20110415, 05:45  #2  
Jun 2003
2^{2}·5·257 Posts 
Quote:


20110415, 09:01  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,939 Posts 
Quote:
It's not a project which I'd be very interested in, TBH. Much more interesting, IMO, is to create a proven prime of some ridiculously large size and high Kolmogorov complexity by driving the N \pm 1 tests in reverse. Paul 

20110415, 12:06  #4  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
10^1000000 + n for Last fiddled with by science_man_88 on 20110415 at 12:08 

20110415, 12:13  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
25273_{8} Posts 
Quote:
I suggest that you try again. Paul P.S. 10^999999+1 is composite. Prove this. 

20110415, 12:18  #6 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 

20110415, 15:35  #7 
Aug 2006
1011101011011_{2} Posts 
axn: In my defense, I intended "tens (not hundreds) of thousands of tests".
I'm not asking how to do it today, but rather how long until it's easy enough that someone says "what the heck, I'll calculate that". Do you think ten years? Twenty? 
20110415, 16:09  #8 
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
11234_{8} Posts 
We can narrow it down to somewhere between:
http://primes.utm.edu/primes/lists/all.txt Code:
rank description digits who year comment 35 59*2^34084161 1026038 L426 2010 36 3139*2^33219051 999997 L185 2008 
20110415, 16:12  #9 
"Forget I exist"
Jul 2009
Dumbassville
20300_{8} Posts 
I can't I know it's 5 mod 6 and 41 mod 120 but that's all I've worked out. I can't remember what else to work out.
Last fiddled with by science_man_88 on 20110415 at 16:16 
20110415, 16:16  #10 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
oh and it's 1 mod 4 by my math. which brings me back ( I believe the rule is 4x+3 as well as 6n+5, if so it can't be prime).

20110415, 16:29  #11 
"Brian"
Jul 2007
The Netherlands
CC6_{16} Posts 
Science Man, is there anything you notice about the numbers , , , ... ,, ... and can you prove the property for all n?

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SciTech extrapolation into SciFi.  jwaltos  Reading  0  20171031 19:00 
Estimating minimum relations  bchaffin  Factoring  24  20120324 18:37 
Using long long's in Mingw with 32bit Windows XP  grandpascorpion  Programming  7  20091004 12:13 
I think it's gonna be a long, long time  panic  Hardware  9  20090911 05:11 
Msieve NFS minimum size  10metreh  Msieve  35  20090402 19:14 