mersenneforum.org Sieving freakishly big MMs (was "World record" phone number?)
 Register FAQ Search Today's Posts Mark Forums Read

2012-09-23, 21:51   #12
davieddy

"Lucan"
Dec 2006
England

2·3·13·83 Posts

Quote:
 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

2012-09-24, 01:47   #13
jasong

"Jason Goatcher"
Mar 2005

3×7×167 Posts

Quote:
 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.

2012-09-24, 02:19   #14
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts

Quote:
 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.

2012-09-24, 02:34   #15
jasong

"Jason Goatcher"
Mar 2005

3×7×167 Posts

Quote:
 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 :)

2012-09-24, 02:43   #16
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts

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

2012-09-24, 05:17   #17
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

968710 Posts

Quote:
 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!

Last fiddled with by Batalov on 2012-09-24 at 05:23

 2012-09-24, 06:56 #18 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 268416 Posts 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
2012-09-24, 07:22   #19
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

22×3×17×31 Posts

Quote:
 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?

2012-09-24, 12:23   #20
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 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.

Last fiddled with by science_man_88 on 2012-09-24 at 12:24

 2012-09-24, 13:18 #21 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts Mp mod 2 to 1000 Code: 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 ? Last fiddled with by science_man_88 on 2012-09-24 at 13:53
2012-09-24, 13:35   #22
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

632410 Posts

Quote:
 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!).

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Number Theory Discussion Group 51 2018-12-16 21:55 LaurV Hobbies 74 2018-07-11 19:33 Batalov Computer Science & Computational Number Theory 40 2013-03-16 09:19 outlnder Soap Box 20 2005-02-03 09:30 nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 10:30.

Wed Jan 19 10:30:34 UTC 2022 up 180 days, 4:59, 0 users, load averages: 1.76, 1.48, 1.37