20050304, 00:01  #1 
Aug 2004
Melbourne, Australia
152_{10} 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 4n1 (ie. a Lucasian prime) we use a theorem of Euler's to show that q divides 2^p1, and hence 2^p1 is composite. If my calculations are correct, the number of digits of 2^p1 is roughly 10^36523. Does anyone know of any larger Mersenne composites with prime exponents?  Dougy 
20050304, 19:07  #2 
"Phil"
Sep 2002
Tracktown, U.S.A.
1120_{10} Posts 
This is an interesting question. Note that large as your 2^p1 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^209960111)+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? 
20050304, 19:33  #3  
∂^{2}ω=0
Sep 2002
República de California
5×2,351 Posts 
Quote:
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 smallestpossible candidates k = 1 for a bunch of knowncomposite 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 

20050304, 23:09  #4 
"Phil"
Sep 2002
Tracktown, U.S.A.
2^{5}×5×7 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^p1 are roughly 1/k. Of course this can't be exactly right, since if k = 1, 2p+1 is a divisor of 2^p1 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^209960111)+1 has no divisors less than 2^32. Then I used the new version of Prime95 to run P1 and ECM on this number, which is also 2^2099601515. I ran P1 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^240365831)+1 and 2*45*(2^259649511)+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. 
20050311, 12:14  #5 
Aug 2004
Melbourne, Australia
152_{10} 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^30021. 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  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Mersenne prime exponent not randomly distributed?  alpertron  Math  78  20191002 14:31 
Large runs of Mersenne composites  manasi  Prime Gap Searches  3  20170629 13:05 
Mersenne Prime Exponent Distribution  PawnProver44  Miscellaneous Math  26  20160318 08:48 
Factorising Mersenne composites  CuriousKit  PrimeNet  7  20151015 19:25 
Fun with the new Mersenne prime exponent  ewmayer  Lounge  4  20060906 20:57 