My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
December 10th, 2007, 09:45 PM   #1
Senior Member
 
Joined: Nov 2007

Posts: 258
Thanks: 0

"recurrent" mersenne primes

Is there a prime p for which M(p) = 2^p-1 is prime, and also M(M(p)), and also M(M(M(p))), etc.? Imagine if there was such a prime for which M(p) was always prime... the days of GIMPS would be well over! Hehe.
brunojo is offline  
 
December 11th, 2007, 05:04 AM   #2
Senior Member
 
Joined: Dec 2006

Posts: 1,111
Thanks: 0

I severely doubt that. The odds of finding a simple formula that turns out nothing but primes doesn't seem to be a likely thing, at least to me.
Infinity is offline  
December 11th, 2007, 05:25 AM   #3
Senior Member
 
Joined: Nov 2007

Posts: 258
Thanks: 0

I was mostly kidding about such a prime. However I'm still curious to see if there are any mersenne primes for which 2^m-1 is also prime and so on?
For instance 31 is a mersenne prime, as well as 2^31-1.
127 also.
brunojo is offline  
December 11th, 2007, 05:42 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
M(M(2)) is a 1-digit prime.
M(M(3)) is a 3-digit prime.
M(M(5)) is a 10-digit prime.
M(M(7)) is a 39-digit prime.
M(M(11)) is a 617-digit composite.
M(M(13)) is a 2,466-digit composite.
M(M(17)) is a 39,457-digit composite.
M(M(19)) is a 157,827-digit composite.
M(M(23)) is a 2,525,223-digit composite.
M(M(29)) is a 161,614,249-digit composite.
M(M(31)) is a 646,456,993-digit composite.
M(M(37)) is a 41,373,247,568-digit composite.
M(M(41)) is a 661,971,961,084-digit composite.
M(M(43)) is a 2,647,887,844,335-digit composite.
M(M(47)) is a 42,366,205,509,364-digit composite.
M(M(53)) is a 2,711,437,152,599,296-digit composite.
M(M(59)) is a 173,531,977,766,354,911-digit composite.
M(M(61)) has 694,127,911,065,419,642 digits.


The deepest recursion: M(M(M(M(2)))) = 170141183460469231731687303715884105727 is prime.
CRGreathouse is offline  
December 11th, 2007, 02:37 PM   #5
Senior Member
 
Joined: Nov 2007

Posts: 258
Thanks: 0

Nice! you totally rule, Greathouse.
I know it's not known whether there are infinitely many mersenne primes, but, if it was proven that there are, my next question would be : are there sequences of such recurring primes of any arbitrary length?
brunojo is offline  
December 11th, 2007, 09:31 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
I will ponder this question.
CRGreathouse is offline  
December 13th, 2007, 05:26 AM   #7
Senior Member
 
Joined: Dec 2006

Posts: 1,111
Thanks: 0

Quote:
are there sequences of such recurring primes of any arbitrary length?
That's a hard question to answer. I'm not sure how you would go about proving that one...

I guess the big problem is that you would not know exactly where the recurring sequence of arbitrary length was, so you would still have to check all of the primes you got, and you would only know that the sequence existed after you had gone through the usual primality checking of all the possible candidates. Thus, I imagine that the knowledge of the existence of such sequences would not speed up the finding of Mersenne primes.
Infinity is offline  
December 13th, 2007, 09:28 AM   #8
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Good heuristics suggest a chance of about
e^gamma (1.8 + lg p)/p
that a prime p is a Mersenne prime. Since the sum of the reciprocal of the primes diverges, the expected number of Mersenne primes also diverges since the above expression is greater than 1/p. Iterated Mersenne primes are somewhat rarer than you might expect, since Mersenne primes are always 3 mod 4 and exponents which are 1 mod 4 are more likely to produce Mersenne primes.

Taking these things into account, the chance that a Mersenne prime with index p is also the index for the double Mersenne prime 2^(2^p-1)-1 is roughly
e^gamma (p lg (p+1))/2^p

Ignoring (!) the condition that M(p) be prime, which condition is assumed in the above formula, the expected number of double Mersenne primes with index > 13 is about 0.0013. Since we know that there are no double Mersenne numbers with index between 13 and 59 inclusive, we can calculate the expected number of double Mersenne primes as
4 + sum(p = 61, infinity, formula above). But the sum over all primes from 61 on is just 2.86 e-16, so there are most probably only a finite number of double Mersenne primes, with overwhelming chance of there being either 4 or 5.

Of course this is not a proof. Actual results may vary. Talk to your healthcare professional to see if the Wagstaff heuristic is right for you.
CRGreathouse is offline  
December 13th, 2007, 10:16 AM   #9
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Actually looking back at it I'm not sure about the 1 or 3 mod 4 stuff*, but either way the infinite sum is convergent with an expected value of what I posted (since it's a small term and I didn't post many digits).

This does heuristically solve brunojoyal's question: there are expected to be a finite number of prime M(M(p)), and this would imply that there are not iterated Mersenne numbers of arbitrary depth. M(M(M(M(2)))) has four recursions, and it's unlikely anything else will match this.

* If I got it wrong, replace the 1 in the second equation with lg 6.
CRGreathouse is offline  
July 1st, 2008, 07:18 AM   #10
Member
 
Joined: Jul 2008

Posts: 38
Thanks: 0

Re: "recurrent" mersenne primes

M(M(2)) is a 1-digit prime.
M(M(3)) is a 3-digit prime.
M(M(5)) is a 10-digit prime.
M(M(7)) is a 39-digit prime.
M(M(11)) is a 617-digit composite.
M(M(13)) is a 2,466-digit composite.
M(M(17)) is a 39,457-digit composite.
M(M(19)) is a 157,827-digit composite.
M(M(31)) is a 646,456,993-digit composite.
M(M(61)) is a 694,127,911,065,419,642-digit composite.
M(M(89)) is a 186,328,542,329,173,367,306,815,834-digit composite.
M(M(107)) is a 48,844,909,400,338,823,199,277,929,902,126-digit composite.
M(M(127)) is a 51,217,599,719,369,681,875,006,054,625,051,616,350-digit prime.
nobody is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
mersenne, primes, recurrent



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
A "simple" application of dirac delta "shift theorem"...help SedaKhold Calculus 0 February 13th, 2012 12:45 PM
"separate and integrate" or "Orangutang method" The Chaz Calculus 1 August 5th, 2011 10:03 PM
sample exeriment-need help finding "statistic" and "result" katie0127 Advanced Statistics 0 December 3rd, 2008 02:54 PM
terms "non-increasing" or "non-decreasing" Ujjwal Number Theory 2 September 29th, 2008 08:06 AM





Copyright © 2017 My Math Forum. All rights reserved.