mersenneforum.org > Math Extrapolation: How long until the minimum megaprime?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-04-15, 03:40 #1 CRGreathouse     Aug 2006 135418 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).
2011-04-15, 05:45   #2
axn

Jun 2003

115518 Posts

Quote:
 Originally Posted by CRGreathouse 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).
ln(10^999999) / (e^gamma ln(10^14)) ~= 40000 expected prp tests.

2011-04-15, 09:01   #3
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

101001101111102 Posts

Quote:
 Originally Posted by CRGreathouse Unlike finding it, proving its primality might not be possible in my lifetime, barring breakthroughs in algorithms (not particularly unlikely, I suppose).
It might be possible, but very very unlikely. Enough factors may be found of N \pm 1, and enough of their factors, and so on...

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

2011-04-15, 12:06   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by CRGreathouse 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).
as 10^1000000 is 4 mod 6 the first possible prime is 10^1000000 + 1 and if within the first 100 after that it must follow:

10^1000000 + n for $n \in \{{1,5,7,.......}\}
$

Last fiddled with by science_man_88 on 2011-04-15 at 12:08

2011-04-15, 12:13   #5
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×3×13×137 Posts

Quote:
 Originally Posted by science_man_88 as 10^1000000 is 4 mod 6 the first possible prime is 10^1000000 + 1 and if within the first 100 after that it must follow: 10^1000000 + n for $n \in \{{1,5,7,.......}\}$
It's easy to show that 10^1000000 has 1000001 digits and so is much larger than the first megaprime.

I suggest that you try again.

Paul

P.S. 10^999999+1 is composite. Prove this.

2011-04-15, 12:18   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 Originally Posted by xilman It's easy to show that 10^1000000 has 1000001 digits and so is much larger than the first megaprime. I suggest that you try again. Paul P.S. 10^999999+1 is composite. Prove this.
I forget some times at least I'm trying. lol

2011-04-15, 15:35   #7
CRGreathouse

Aug 2006

176116 Posts

axn: In my defense, I intended "tens (not hundreds) of thousands of tests".

Quote:
 Originally Posted by xilman It might be possible, but very very unlikely. Enough factors may be found of N \pm 1, and enough of their factors, and so on... It's not a project which I'd be very interested in, TBH.
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?

 2011-04-15, 16:09 #8 petrw1 1976 Toyota Corona years forever!     "Wayne" Nov 2006 Saskatchewan, Canada 2×3×773 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^3408416-1 1026038 L426 2010 36 3139*2^3321905-1 999997 L185 2008
2011-04-15, 16:12   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by xilman It's easy to show that 10^1000000 has 1000001 digits and so is much larger than the first megaprime. I suggest that you try again. Paul P.S. 10^999999+1 is composite. Prove this.
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 2011-04-15 at 16:16

 2011-04-15, 16:16 #10 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·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).
 2011-04-15, 16:29 #11 Brian-E     "Brian" Jul 2007 The Netherlands 7·467 Posts Science Man, is there anything you notice about the numbers $10^1+1$, $10^3+1$, $10^5+1$, ... ,$10^{(2n+1)}+1$, ... and can you prove the property for all n?

 Similar Threads Thread Thread Starter Forum Replies Last Post jwaltos Reading 0 2017-10-31 19:00 bchaffin Factoring 24 2012-03-24 18:37 grandpascorpion Programming 7 2009-10-04 12:13 panic Hardware 9 2009-09-11 05:11 10metreh Msieve 35 2009-04-02 19:14

All times are UTC. The time now is 03:46.

Tue May 18 03:46:48 UTC 2021 up 39 days, 22:27, 0 users, load averages: 3.66, 3.17, 2.84