mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-03-04, 00:01   #1
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23×19 Posts
Question Mersenne composites (with prime exponent)

G'day,
Just wondering if anyone has got a collection of the largest known Mersenne numbers with prime exponents.

According to Mathworld p = 7068555.(2^121301)-1 and q = 2p+1 = 7068555.(2^121302)-1 is the largest known Sophie Germain prime. Since p is of the form 4n-1 (ie. a Lucasian prime) we use a theorem of Euler's to show that q divides 2^p-1, and hence 2^p-1 is composite.

If my calculations are correct, the number of digits of 2^p-1 is roughly 10^36523.

Does anyone know of any larger Mersenne composites with prime exponents?

- Dougy
Dougy is offline   Reply With Quote
Old 2005-03-04, 19:07   #2
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111002 Posts
Default

This is an interesting question. Note that large as your 2^p-1 is, it is still miniscule compared to the largest known composite Fermat number F(2478782)! I see that the largest known Sophie Germain prime entry has roughly doubled in number of digits in the past 5 years, so I wouldn't expect that looking for larger S.G. primes is going to lead to any dramatic breakthroughs. I have been searching recently for factors of large iterated Mersenne numbers M(M(p)) where M(p) is a Mersenne prime. Will Edgington keeps a webpage of progress on these numbers at:
http://www.garlic.com/~wedgingt/MMPstats.txt
I am currently testing 16*(2^20996011-1)+1 to see if it is a factor of M(M(20996011)), but I estimate that my chances of success are roughly 1 in 2.5 million. There are now 42 of these iterated Mersenne numbers known, but no factors are known for any larger than M(M(31)), so I don't expect any sudden progress in the near future. But there must be an easier way to increase the upper bound of largest known composite Mersenne number (with prime number exponent). Ideas, anyone?
philmoore is offline   Reply With Quote
Old 2005-03-04, 19:33   #3
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

100110001111112 Posts
Default

Quote:
Originally Posted by philmoore
I am currently testing 16*(2^20996011-1)+1 to see if it is a factor of M(M(20996011)), but I estimate that my chances of success are roughly 1 in 2.5 million.
Hi, Phil:

Why so low? On average, factor candidates 2*k*p + 1 with small k have a relatively much larger chance of being factors than those with large k, that's why even if one tries just the smallest-possible candidates k = 1 for a bunch of known-composite Mersennes, one will generally find some nontrivial fraction to be factors. Could you explain the heuristics you used to arrive at your probabilistic estimate?

-Ernst
ewmayer is offline   Reply With Quote
Old 2005-03-04, 23:09   #4
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22×32×31 Posts
Default

Those odds are really just a guess. I arrived at it by analogy with Fermat numbers. I believe it was a conjecture of Keller that if k*2^m+1 is prime, the probability of it dividing some Fermat number seem to be about 1/k. So I guessed by analogy that if p is prime and 2*k*p+1 is also prime, then the odds of 2*k*p+1 being a divisor of 2^p-1 are roughly 1/k. Of course this can't be exactly right, since if k = 1, 2p+1 is a divisor of 2^p-1 only when p is = 3 mod 4. (Otherwise, it divides 2^p+1.) Still, for the sake of argument, take my case of k=8. I checked first that 16*(2^20996011-1)+1 has no divisors less than 2^32. Then I used the new version of Prime95 to run P-1 and ECM on this number, which is also 2^20996015-15. I ran P-1 to bounds B1=250,000 and B2=10,000,000 and then I ran 15 ECM curves to bounds B1=11,000 and B2=1,100,000. (In retrospect, I wish I had run 33 curves with B1=5000 and B2=500,000 instead.) Now, I am estimating that I certainly would have found any factors of at least up to 40 bits, this raises the probability that my number is prime to about 1 in 300,000. But if it then has only a 1 in 8 chance of dividing M(M(20996011)), that puts my overall chances as 1 in 2,400,000. That may be an underestimate, but I still don't expect the odds to be too much better than 1 in 2 million. I would enjoy hearing any comments anyone may have.

After this one, I plan to test 2*48*(2^24036583-1)+1 and 2*45*(2^25964951-1)+1 as well, but because of the larger k values, I really think that my current test presents the best probability of finding a factor of a large iterated Mersenne number.
philmoore is offline   Reply With Quote
Old 2005-03-11, 12:14   #5
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

2308 Posts
Default

Okay, I hope my calculations are correct, but the number of digits of F2478785 = 2^(2^2478785)+1 is greater than 10^746187. So this is phenomonally bigger then the largest known mersenne number with prime exponent.

P. Ribenboim, The Book of Prime Number Records (1988): The largest known composite Mersenne number is Mq with q = 16695*2^3002-1. 2q+1 is prime. (or at least probably)

Obviously this out out of date, but this used Euler's theorem to find the largest known Mersenne composite (with prime exponent), and I haven't heard of any other theorems that will give other Mersenne composites. So perhaps the same method is still valid at this stage.
Dougy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne prime exponent not randomly distributed? alpertron Math 78 2019-10-02 14:31
Large runs of Mersenne composites manasi Prime Gap Searches 3 2017-06-29 13:05
Mersenne Prime Exponent Distribution PawnProver44 Miscellaneous Math 26 2016-03-18 08:48
Factorising Mersenne composites CuriousKit PrimeNet 7 2015-10-15 19:25
Fun with the new Mersenne prime exponent ewmayer Lounge 4 2006-09-06 20:57

All times are UTC. The time now is 18:15.

Sat Oct 24 18:15:24 UTC 2020 up 44 days, 15:26, 1 user, load averages: 2.08, 1.89, 1.87

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.