mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2011-04-15, 03:40   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default 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).
CRGreathouse is offline   Reply With Quote
Old 2011-04-15, 05:45   #2
axn
 
axn's Avatar
 
Jun 2003

22·5·257 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
axn is offline   Reply With Quote
Old 2011-04-15, 09:01   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

10,939 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
xilman is offline   Reply With Quote
Old 2011-04-15, 12:06   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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,.......}\}<br />

Last fiddled with by science_man_88 on 2011-04-15 at 12:08
science_man_88 is offline   Reply With Quote
Old 2011-04-15, 12:13   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

252738 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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,.......}\}<br />
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.
xilman is offline   Reply With Quote
Old 2011-04-15, 12:18   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by xilman View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-04-15, 15:35   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111010110112 Posts
Default

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

Quote:
Originally Posted by xilman View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2011-04-15, 16:09   #8
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

112348 Posts
Default

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
petrw1 is offline   Reply With Quote
Old 2011-04-15, 16:12   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by xilman View Post
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
science_man_88 is offline   Reply With Quote
Old 2011-04-15, 16:16   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

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).
science_man_88 is offline   Reply With Quote
Old 2011-04-15, 16:29   #11
Brian-E
 
Brian-E's Avatar
 
"Brian"
Jul 2007
The Netherlands

CC616 Posts
Default

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?
Brian-E is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sci-Tech extrapolation into Sci-Fi. jwaltos Reading 0 2017-10-31 19:00
Estimating minimum relations bchaffin Factoring 24 2012-03-24 18:37
Using long long's in Mingw with 32-bit Windows XP grandpascorpion Programming 7 2009-10-04 12:13
I think it's gonna be a long, long time panic Hardware 9 2009-09-11 05:11
Msieve NFS minimum size 10metreh Msieve 35 2009-04-02 19:14

All times are UTC. The time now is 06:49.


Sat Oct 16 06:49:54 UTC 2021 up 85 days, 1:18, 0 users, load averages: 1.44, 1.21, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.