Extrapolation: How long until the minimum megaprime?

[science_man_88]

Originally Posted by science_man_88

(17:49)>for(y=2,300,for(x=1,300,if(((10^x)%y)==((10^(x+1))%y),print(x" "y" "10^x%y);break())))
1 2 0
1 3 1
2 4 0
1 5 0
1 6 4
3 8 0
1 9 1
1 10 0
2 12 4
1 15 10
4 16 0
1 18 10
2 20 0
3 24 16
2 25 0
1 30 10
5 32 0
2 36 28
3 40 0
1 45 10
4 48 16
2 50 0
2 60 40
6 64 0
3 72 64
2 75 25
4 80 0
1 90 10
5 96 64
2 100 0
3 120 40
3 125 0
7 128 0
4 144 64
2 150 100
5 160 0
2 180 100
6 192 64
3 200 0
2 225 100
4 240 160
3 250 0
8 256 0
5 288 64
2 300 100

this can tell us loads up to x=300 ( though it doesn't have the range of y necessary) for example all 10^x for x>=2 are 40 mod 60 ( which is almost the same but stronger than 40 mod 120 for x>=3).

I realized something we only need to check odd (prime ?) y to help us doh.

[chris2be8]

Originally Posted by science_man_88

I realized something we only need to check odd (prime ?) y to help us doh.

Try multiplying out (x^333333+1)(x^666666-x^333333+1). Then work out the total number of algebraic factors 10^999999+1 will have.

Chris K

[science_man_88]

Originally Posted by chris2be8

Try multiplying out (x^333333+1)(x^666666-x^333333+1). Then work out the total number of algebraic factors 10^999999+1 will have.

Chris K

here's a way mod it by a high (primorial(all primes)/2) that way we reduce the number to deal with.

[science_man_88]

Originally Posted by science_man_88

the problem is setting up a set {11,1001,100001,.....} and proving the first ( obvious) and then going to a formula to prove that if one has it then the next has it I've read up. so that's the hard part. basis:11 is obviously divisible by 11, induction: from the recurrence of 100*a(n-1)-99 if a(n-1) |11 then 100 * it will and 99 is |11 so it still becomes |11. so if one a(n) is divisible by 11 they all are. yeah I know a long stretch.

he gave hints through PM.

[science_man_88]

Originally Posted by science_man_88

he gave hints through PM.

okay my wording is crap and it should be a sequence not a set.

[R.D. Silverman]

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

Where did the number 10,000 come from?

Finding the smallest prime number N with 1 million digits is way way beyond
today's capabilities unless by some extraordinary luck it
has some special feature that allows finding sufficiently many
factors of N-1 or N+1.

IF one assumes the GRH, then 2 log^2(N) prp tests will suffice.
[via a thm. of E. Bach]

[CRGreathouse]

Originally Posted by R.D. Silverman

Where did the number 10,000 come from?

It's just an order-of-magnitude on Mertens' theorem -- tens, not hundreds, of thousands of candidates would need to be examined on average.

Originally Posted by R.D. Silverman

Finding the smallest prime number N with 1 million digits is way way beyond
today's capabilities unless by some extraordinary luck it
has some special feature that allows finding sufficiently many
factors of N-1 or N+1.

Right -- this would take too many resources today to be practical. So when might it be? I certainly don't think it will take 300 years to resolve, but I don't expect it will be computed this decade either. What do you think?

It's your intuition, and that of others in the field, that I'm curious about in making this post.

Note that I'm not talking about proving primality (which is far beyond present capabilities) but merely *finding* the smallest megaprime (which is beyond practical capabilities at the moment).

Originally Posted by R.D. Silverman

IF one assumes the GRH, then 2 log^2(N) prp tests will suffice.
[via a thm. of E. Bach]

Isn't that under the ERH? Actually that seems more plausible than I had thought -- easily possible under the Erdős-type scenario "aliens will destroy the world unless you prove this", taking probably less than a year with all the world's hardware.

Though I'm not interested in proving, just finding.

[R.D. Silverman]

Originally Posted by CRGreathouse

It's just an order-of-magnitude on Mertens' theorem -- tens, not hundreds, of thousands of candidates would need to be examined on average.



Right -- this would take too many resources today to be practical. So when might it be? I certainly don't think it will take 300 years to resolve, but I don't expect it will be computed this decade either. What do you think?

It's your intuition, and that of others in the field, that I'm curious about in making this post.

Note that I'm not talking about proving primality (which is far beyond present capabilities) but merely *finding* the smallest megaprime (which is beyond practical capabilities at the moment).



Isn't that under the ERH? Actually that seems more plausible than I had thought -- easily possible under the Erdős-type scenario "aliens will destroy the world unless you prove this", taking probably less than a year with all the world's hardware.

Though I'm not interested in proving, just finding.

Generalized Riemann Hypothesis == Extended Riemann Hypothesis....

[CRGreathouse]

Originally Posted by R.D. Silverman

Generalized Riemann Hypothesis == Extended Riemann Hypothesis....

I think of them as different statements, as (e.g.) Dr. Caldwell writes:
http://primes.utm.edu/notes/rh.html#erh

[science_man_88]

I see ways to limit the values it could be significantly I think.

2+4+2+4+2 = 14
4+2+4+2+4+2+4+2+4 =28

using these 2 after finding a n such that 10^x+n is 0 mod 7 can eliminate all multiples of 7. this would remove about 2/42 candidates ( in the range of 9* 10^999999 range before 10^1000000, that's quite a few).

I haven't quite done anything for any other primes.

[science_man_88]

Originally Posted by science_man_88

I see ways to limit the values it could be significantly I think.

2+4+2+4+2 = 14
4+2+4+2+4+2+4+2+4 =28

using these 2 after finding a n such that 10^x+n is 0 mod 7 can eliminate all multiples of 7. this would remove about 2/42 candidates ( in the range of 9* 10^999999 range before 10^1000000, that's quite a few).

I haven't quite done anything for any other primes.

the multiples that work for 11 are 44 ( for the starts and ends with 2) and 22 ( for the starts and ends with 4).