mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Lounge

Reply
 
Thread Tools
Old 2003-12-14, 08:51   #1
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2·3·293 Posts
Default Recursive Primes?

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
jinydu is offline   Reply With Quote
Old 2003-12-14, 10:24   #2
patrik
 
patrik's Avatar
 
"Patrik Johansson"
Aug 2002
Uppsala, Sweden

1A916 Posts
Default Re: Recursive Primes?

Quote:
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.
patrik is offline   Reply With Quote
Old 2003-12-14, 12:05   #3
nfortino
 
nfortino's Avatar
 
Nov 2003

3×5×11 Posts
Default

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 2M127-1 for primality.
nfortino is offline   Reply With Quote
Old 2003-12-14, 13:35   #4
andi314
 
andi314's Avatar
 
Nov 2002

1128 Posts
Default

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!!
andi314 is offline   Reply With Quote
Old 2003-12-14, 14:36   #5
nfortino
 
nfortino's Avatar
 
Nov 2003

A516 Posts
Default

You've probably already thought of this, but by using the successive squaring method, it is much faster to test if 22[sup]127[/sup] == 2 mod p instead of testing if 2M127 == 1 mod p. Because you are only testing numbers of the form 2k*M127+1, which are odd, any factor you find of 22[sup]127[/sup]-2 will be a factor of MM127.
nfortino is offline   Reply With Quote
Old 2003-12-15, 10:12   #6
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

110110111102 Posts
Default

(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 is offline   Reply With Quote
Old 2003-12-15, 11:40   #7
jinydu
 
jinydu's Avatar
 
Dec 2003
Hopefully Near M48

2×3×293 Posts
Default

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?
jinydu is offline   Reply With Quote
Old 2003-12-15, 13:24   #8
andi314
 
andi314's Avatar
 
Nov 2002

2·37 Posts
Default

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!!!
andi314 is offline   Reply With Quote
Old 2003-12-15, 18:06   #9
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

111910 Posts
Default

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.
philmoore is offline   Reply With Quote
Old 2003-12-15, 18:57   #10
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

266328 Posts
Default

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.
ewmayer is offline   Reply With Quote
Old 2003-12-15, 19:19   #11
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

3×373 Posts
Default

ewmayer said:

Quote:
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.
philmoore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 12:56.


Tue Nov 30 12:56:27 UTC 2021 up 130 days, 7:25, 0 users, load averages: 1.21, 1.27, 1.22

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