Recursive Primes?

[jinydu]

I know this sounds obvious, but:

M(2) = (2^2)-1 = 3 Prime
M(3) = (2^3)-1 = 7 Prime
M(7) = (2^7)-1 = 127 Prime
M(127) is prime according to Mathematica 5.0

[patrik]

From http://www.mersenne.org/projects.htm
Tony Forbes is coordinating a search for a factor of MM61 (2^(2^61-1)-1). This is the smallest Mersenne number with a Mersenne prime exponent whose primality status is unknown.

[nfortino]

Actually, you have discovered the Catalan sequence. It is discussed at the bottom of http://www.utm.edu/research/primes/mersenne/ Obviously, it is impossible to check 2^M127-1 for primality.

[andi314]

but we could start a sub project to try to factor MM127.

I'm currently writing a program to fator this huge number

i will then post in the forum when i have completed my work!!

[nfortino]

You've probably already thought of this, but by using the successive squaring method, it is much faster to test if 2^2[sup]127[/sup] == 2 mod p instead of testing if 2^M127 == 1 mod p. Because you are only testing numbers of the form 2k*M127+1, which are odd, any factor you find of 2^2[sup]127[/sup]-2 will be a factor of MM127.

[jinydu]

(2^M127)-1 has over 5.12*10^37 digits!

Only two months ago, I used to think that 10^100 was large beyond comprehension because it overloaded my calculator.

[jinydu]

The new biggest number I can handle is a little bigger than 1.9202*10^646,456,887.

The MaxNumber appears to be exactly

2^([2^31]-[352+1.6017072196434280233747626345680681683204815701770939995185472071170806884765625*10^-16])

So MM31 is "just" out of reach (actually MM31 is over 10^106 times larger).

"but we could start a sub project to try to factor MM127.

I'm currently writing a program to fator this huge number"

How could we do that?

[andi314]

by usind large integer libraries like GMP, miracl or giantint!!! they can hand numbers up to 10 million digits

BUT we dont need to calculate MM127 as a number because we only want to fin a factor( A LL-test is with the todays computers out of reach)

For factoring we use the modular exponation( so the number we are working with is 2*digits of factor maximum!!!

[philmoore]

As noted on Chris Caldwell's webpage linked by nfortino, and also on Will Edgington's status page for iterated Mersenne numbers:
http://www.garlic.com/~wedgingt/MMPstats.txt,
Landon Curt Noll has already checked all possible factors of this number less than 1.02*10^51. If you are really serious about looking for factors of MM127, I would suggest a distributed effort, similar to the distributed effort Tony Forbes has organized for MM61. These numbers seem to be tough, and I would guess that the best chance for finding a factor of one of these numbers lies with MM89, MM107, or MM127.

[ewmayer]

MM31 already has 3 known factors. Tony Forbes' code is extremely efficient, and will work on MM89, MM127 etc., not just on MM61.

Viewed statistically, any of these numbers will only have a chance ~50-60% of having a factor small enough to be found via sieve-based factoring. That means that if a small factor is not found for them, we may never know the status of colossi like MM61, MM89, MM127 without some radical breakthrough in factoring algorithms or the mathematical theory of the Mersennes. Even quantum computing will likely not work on such large numbers, because the sheer number of qubits in each (and AFAIK know QC needs to deal with the entire number, which is one big one disadvantage it has over simple sieving) is so large.

[philmoore]

ewmayer said:

Viewed statistically, any of these numbers will only have a chance ~50-60% of having a factor small enough to be found via sieve-based factoring.

Could you elaborate on what you meant by "any of these numbers", Ernst? If you meant the iterated Mersennes from MM61 to MM127, I'm with you, if you also meant any of the iterated Mersennes larger than that, it seems to me that the chances to factor any of those are quite a bit less.