 mersenneforum.org > Math Mersenne composites (with prime exponent)
 Register FAQ Search Today's Posts Mark Forums Read 2005-03-04, 00:01 #1 Dougy   Aug 2004 Melbourne, Australia 23×19 Posts 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   2005-03-04, 19:07 #2 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 22·32·31 Posts 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?   2005-03-04, 19:33   #3
ewmayer
2ω=0

Sep 2002
República de California

2×59×83 Posts 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   2005-03-04, 23:09 #4 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 21348 Posts 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.   2005-03-11, 12:14 #5 Dougy   Aug 2004 Melbourne, Australia 23·19 Posts 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.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Math 78 2019-10-02 14:31 manasi Prime Gap Searches 3 2017-06-29 13:05 PawnProver44 Miscellaneous Math 26 2016-03-18 08:48 CuriousKit PrimeNet 7 2015-10-15 19:25 ewmayer Lounge 4 2006-09-06 20:57

All times are UTC. The time now is 07:35.

Thu Oct 29 07:35:23 UTC 2020 up 49 days, 4:46, 1 user, load averages: 1.28, 1.52, 1.61