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).

[QUOTE=CRGreathouse;258556]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).[/QUOTE]

ln(10^999999) / (e^gamma ln(10^14)) ~= 40000 expected prp tests.

[QUOTE=CRGreathouse;258556]Unlike finding it, proving its primality might not be possible in my lifetime, barring breakthroughs in algorithms (not particularly unlikely, I suppose).[/QUOTE]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

[QUOTE=CRGreathouse;258556]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).[/QUOTE]

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 [TEX]n \in \{{1,5,7,.......}\}
[/TEX]

[QUOTE=science_man_88;258583]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 [TEX]n \in \{{1,5,7,.......}\}
[/TEX][/QUOTE]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. :smile:

Paul

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

[QUOTE=xilman;258585]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. :smile:

Paul

P.S. 10^999999+1 is composite. Prove this.[/QUOTE]

I forget some times at least I'm trying. lol

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

[QUOTE=xilman;258571]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.[/QUOTE]

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?

We can narrow it down to somewhere between:

[url]http://primes.utm.edu/primes/lists/all.txt[/url]
[CODE]rank description digits who year comment
35 59*2^3408416-1 1026038 L426 2010
36 3139*2^3321905-1 999997 L185 2008 [/CODE]

[QUOTE=xilman;258585]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. :smile:

Paul

P.S. 10^999999+1 is composite. Prove this.[/QUOTE]

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.

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, is there anything you notice about the numbers [TEX]10^1+1[/TEX], [TEX]10^3+1[/TEX], [TEX]10^5+1[/TEX], ... ,[TEX]10^{(2n+1)}+1[/TEX], ... and can you prove the property for all n?