Sieving freakishly big MMs (was "World record" phone number?)

[davieddy]

Originally Posted by ATH

"nontrivial Riemann zeta function zeros".

Damn shame his housemaid threw most his writings on the fire after he died far too young.

I should try to publish some more papers.

D

PS Or give up smoking

[jasong]

Originally Posted by ewmayer

I can say with 100% certainty that the smallest prime factor of M(M43112609) is a world record prime, but without an explicit demonstration of such a factor, that is meaningless.

Does that mean there's a mathematical proof that the smallest factor, whatever it is, has more digits than the highest known prime number?

I ask because some people say they're 100% certain about something when it's actually only a strong opinion. Not making any sort of accusation, just asking for clarification.

[Dubslow]

Originally Posted by jasong

Does that mean there's a mathematical proof that the smallest factor, whatever it is, has more digits than the highest known prime number?

I ask because some people say they're 100% certain about something when it's actually only a strong opinion. Not making any sort of accusation, just asking for clarification.

Umm... Mersenne factors of 2^p-1 are of the form q=2*k*p+1, => q > p.

[jasong]

Originally Posted by Dubslow

Umm... Mersenne factors of 2^p-1 are of the form q=2*k*p+1, => q > p.

I'm going to assume from the context of this thread that M43112609 is the highest known Mersenne number. So, the lowest possible factor for MM43112609, assuming no one has ever tried(yes, I know someone almost certainly has) is:

2*1*M43112609+1

Typed it out for anyone that's as slow as I am :)

[Dubslow]

Originally Posted by jasong

I'm going to assume from the context of this thread that M43112609 is the highest known Mersenne number. So, the lowest possible factor for MM43112609, assuming no one has ever tried(yes, I know someone almost certainly has) is:

2*1*M43112609+1

Typed it out for anyone that's as slow as I am :)

Wow... this gets dumber and dumber. M43112609 is the largest known prime number, as any decent GIMPSter (or Googler) would know.

Finally, from the math page, it requires O(p) squarings mod q to test if q divides 2^p-1; given the absolutely gargantuan values of p and q, I'm relatively sure that no one has tried (it would take about as much work, asymptotically speaking, to test 2^p-1%q as to test p for primality with the LL test).

[Batalov]

Originally Posted by jasong

I'm going to assume from the context of this thread that M43112609 is the highest known Mersenne number. So, the lowest possible factor for MM43112609, assuming no one has ever tried(yes, I know someone almost certainly has) is:

2*1*M43112609+1

Typed it out for anyone that's as slow as I am :)

2*1*M43112609+1 is divisible by 3.
2*2*M43112609+1 is divisible by 5.
...
k>=5 dude. (Common knowledge for MMp.) Sieve a little bit, then do what KEP did; maybe one of you will get lucky!

[LaurV]

In fact, as Mp is 3 mod 4, when looking for factors of MMp of the form q=2*k*Mp+1, we are interested only in k=0,1 (mod 4). So, k can only be 1,4,5,8,9,12,13,16,17, etc.
But as Batalov pointed, for k=1 (therefore 1,4,7,10,13,etc) all q's are 0 mod 3, because Mp is 1 mod 3. Same for mod 5, Mp=1, so k=2,7,12,17,22,27,32,etc are all excluded. Mp=3 (mod 7) so for all k=1,8,15,22,29, etc results in q's being 0 mod 7.
etc
etc
Intersecting all this stuff, the most k's are gone very fast. Using primes below 1M, very few k remain.
k=5 will be gone if we extend higher, 2*5*Mp+1 is divisible with 582994261.
Next k which does not... succumb under the filter with small primes is k=185 (tested with primes under 1G4), and behind of it, k=201.

So, if someone can prove that 2*185*Mp+1 is prime, be my guest

[retina]

Originally Posted by LaurV

So, if someone can prove that 2*185*Mp+1 is prime, be my guest

Oh, this one is easy to prove prime using the "Terrence Law" method. No small factors have been found, so 2*185*M43112609+1 is prime

What do I win?

[science_man_88]

Originally Posted by LaurV

In fact, as Mp is 3 mod 4, when looking for factors of MMp of the form q=2*k*Mp+1, we are interested only in k=0,1 (mod 4). So, k can only be 1,4,5,8,9,12,13,16,17, etc.
But as Batalov pointed, for k=1 (therefore 1,4,7,10,13,etc) all q's are 0 mod 3, because Mp is 1 mod 3. Same for mod 5, Mp=1, so k=2,7,12,17,22,27,32,etc are all excluded. Mp=3 (mod 7) so for all k=1,8,15,22,29, etc results in q's being 0 mod 7.
etc
etc
Intersecting all this stuff, the most k's are gone very fast. Using primes below 1M, very few k remain.
k=5 will be gone if we extend higher, 2*5*Mp+1 is divisible with 582994261.
Next k which does not... succumb under the filter with small primes is k=185 (tested with primes under 1G4), and behind of it, k=201.

So, if someone can prove that 2*185*Mp+1 is prime, be my guest

okay I'm lost k=185 has k=3 mod 7, 2*3*3+1 = 18+1 = 19 mod 7 = 5 mod 7 this is not q=0 mod 7 doh misread it all.

[science_man_88]

Mp mod 2 to 1000

1,1,3,1,1,3,7,4,1,5,7,5,3,1,15,1,13,9,11,10,5,1,7,11,5,13,3,1,1,15,31,16,1,31,31,17,9,31,31,19,31,1,27,31,1,16,31,10,11,1,31,30,13,16,31,28,1,30,31,29,15,31,63,31,49,6,35,1,31,9,31,36,17,61,47,38,
31,8,31,67,19,78,31,1,1,1,71,1,31,31,47,46,63,66,31,24,59,49,11,6,1,6,31,31,83,62,67,53,71,91,31,1,85,1,59,31,89,52,31,5,29,19,15,11,31,1,127,1,31,87,115,66,73,121,103,119,1,91,31,16,9,5,31,1,109,10,91,
49,61,75,47,103,115,46,31,28,87,136,31,24,67,147,19,16,161,3,31,70,1,85,87,96,1,136,159,148,1,57,31,89,31,151,47,91,139,137,63,94,161,2,127,167,121,31,59,158,49,150,111,73,107,59,103,101,109,139,31,
104,31,190,83,151,169,1,175,108,53,109,71,18,91,33,31,211,1,196,199,176,1,115,175,75,31,16,207,166,171,71,31,208,5,67,151,206,19,161,15,244,11,9,31,93,1,1,255,1,1,17,31,175,87,203,247,136,199,1,207,
155,121,120,239,31,119,236,139,37,91,139,31,179,157,57,151,256,5,101,31,35,1,121,255,113,157,266,239,148,49,70,211,87,75,208,47,151,103,193,115,109,201,62,31,288,185,31,87,124,295,291,191,169,185,
256,67,161,147,271,183,157,181,165,327,202,3,6,31,255,239,1,171,170,85,255,87,1,269,163,175,49,311,148,159,1,325,151,179,52,57,218,31,142,89,247,31,36,151,31,47,265,91,136,139,213,137,136,63,291,
283,122,351,1,193,27,127,346,167,130,315,33,31,1,255,349,355,166,247,1,349,199,111,110,73,356,107,391,59,313,103,159,101,256,315,325,139,161,31,91,313,97,31,344,401,157,295,86,151,395,383,148,1,
297,175,305,325,1,271,47,109,55,71,157,239,401,91,1,33,49,255,1,211,60,227,226,423,31,199,422,405,256,231,453,115,41,175,46,75,223,31,73,251,28,207,302,403,161,171,454,71,137,31,239,449,346,247,
121,67,268,151,310,451,118,19,1,161,346,15,80,493,494,11,337,9,91,31,6,93,70,255,202,1,255,511,256,1,6,259,16,17,442,31,369,175,247,87,136,203,511,511,323,401,148,199,265,1,276,207,415,155,500,
391,64,391,451,511,271,31,477,119,517,511,465,415,87,37,91,91,22,139,44,31,511,179,294,439,1,57,472,151,281,541,488,291,193,101,461,319,92,35,553,291,493,121,401,255,31,113,7,451,294,561,355,239,
123,445,171,347,349,369,341,511,511,87,274,75,126,511,141,351,262,151,486,103,192,193,511,423,1,109,614,511,553,373,535,31,11,601,313,499,239,31,315,87,190,441,1,295,304,291,364,511,638,169,632,
507,1,579,24,391,148,161,325,147,423,271,611,511,328,157,532,511,550,165,460,327,66,535,1,3,256,341,456,31,509,255,661,239,173,1,24,511,196,511,1,427,256,255,634,431,83,1,534,615,346,163,91,175,
511,49,541,311,498,499,313,511,16,1,612,679,78,151,166,535,139,409,291,415,310,577,168,31,521,503,208,451,436,247,452,31,67,401,1,151,31,31,451,415,676,265,734,91,655,507,172,511,496,213,742,
511,276,511,433,63,511,291,226,283,318,501,346,351,367,1,598,575,256,27,148,511,606,731,1,167,362,517,511,703,535,33,142,31,577,1,175,255,656,349,270,355,466,561,227,247,395,1,136,747,289,199,
392,511,535,511,401,475,346,759,424,511,637,391,64,59,391,313,636,511,560,159,31,511,491,667,651,727,511,325,469,139,34,161,37,447,647,91,671,731,418,97,285,31,581,765,460,823,746,157,731,
719,340,511,461,151,274,395,256,383,742,577,308,431,388,297,817,607,96,305,613,759,324,1,408,271,121,47,136,547,141,55,406,511,44,157,626,239,856,401,333,535,255,1,148,479,674,49,236,255,70,
1,697,211,613,511,388,679,451,679,72,423,814,31,241,655,742,879,151,863,87,715,102,231,193,453,577,115,461,41,418,639,112,511,598,75,373,223,511,31,782,73,601,251,362,499,921,207,661,775,283,
403,109,161,124,647,833,931,766,71,610,137,941,511,418,239,490,931,746,829,247,247,256,121,741,67,647,755,811,639,944,799,357,451,598,609,468,511,946,1,157,655,1,841,24,511,496,577,946,991,
352,993,202,511,

what does this tell us ?

[retina]

Originally Posted by science_man_88

what does this tell us ?

1. That you have a program that can calculate residues.

2. That Mp is not division by any number <=1000.

3. That your unformatted code forces me to scroll sideways (yuck!).