20030806, 16:28  #1 
Sep 2002
1010010110_{2} Posts 
Search for Mersenne primes by checking for perfect numbers
After reading http://www.utm.edu/research/primes/mersenne/ and finding the link between perfect numbers and mersenne primes,
with each perfect number the product of a number times a mersenne prime, I wonder if a search for perfect numbers would be useful for finding mersenne primes. There seems to be fewer perfect numbers then mersenne primes ( for a given range ), some of the mersenne primes aren't factors of a perfect number. So this strategy will skip some mersenne primes but still may find some that were missed or not yet found. The binary format for perfect numbers seems amenable for a program, 1s followed by 0s and the test: convert to decimal then keep adding the digits until only one digit remains, if it is 1 then it is a perfect number. The prime exponents Prime95 is dealing with would be under 10 million bytes. Example p = 24 000 000 , so it is the same number of bits, divide by 8 to get bytes equals 3 000 000 bytes. This may only get a mersenne prime of roughly 1/2 p so doubling the size of p to 48 000 000 would give 6 million bytes and should put it back in range. Given x number of bits would give roughly x/2 for p. The coding doesn't appear to be hard but I don't know how long it would take to run for each large possible perfect number. I may code it, testing with the smaller numbers first. Is there already someone working on this or is there some other issue(s) (math or programming) that would make this nonviable ? I guess this topic could have gone in the new forum Factoring if it was open. Discovering perfect numbers to get their mersenne prime factor ! 
20030806, 17:43  #2  
Aug 2002
Richland, WA
2^{2}×3×11 Posts 
I think you missed something from that page:
Quote:
As far as I know, an LL test is much faster than any methods we have for finding perfect numbers. 

20030806, 18:48  #3 
Sep 2002
296_{16} Posts 
The very property of perfect numbers that could be exploited is,
if a perfect number then one factor is a mersenne prime. The only (obvious) thing that could derail it is given a number that follows the binary form from the web page, converting it to decimal, repeatedly summing the digits, finally getting one digit with a value of 1, and it not being a perfect number. My understanding was all the perfect numbers followed the binary form given on the web page. As for the speed of this algorithm, that remains to be seen. I was able to match some of the mersenne primes to perfect numbers, some had no obvious pairing. n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127 for mersenne primes. 2.3=6, 4.7=28, 16.31=496, 64.127=8128 as the pairs. Where is the pair for 2,5,13,17,19,61,89,107 ? 
20030806, 18:59  #4  
Aug 2002
Richland, WA
10000100_{2} Posts 
Quote:
2*(2^21) = 6 4*(2^31) = 28 16*(2^51) = 496 . . . 

20030806, 19:04  #5  
Dec 2002
Frederick County, MD
2×5×37 Posts 
Quote:
The first Mersenne prime is 3 (2^21) The second Mersenne prime is 7 (2^31) The third Mersenne prime is 31 (2^51) etc. And these numbers are what you are matching up. edit: Oops, Nick beat me to it. 

20030806, 19:07  #6  
Aug 2002
2·3·5 Posts 
Quote:
n = 3: 2^2 * (2^31) = 28 n = 5: 2^4 * (2^51) = 496 etc. The definition of a perfect number is that it is equal to the sum of all of its factors. In order to find this sum you need to know all of the number's prime factors. Thus you need to check 2^n1 to see if it is prime in order to determine if 2^(n1)(2^n1) is perfect. edit: oops, Nick and eepiccolo beat me to it 

20030806, 19:09  #7  
Aug 2002
Richland, WA
2^{2}·3·11 Posts 
From the fact that even perfect numbers are of the form 2^(n1)*(2^n1), the binary representation must be n 1's followed by n1 0's.
I also do not understand your algorithm for checking if a number is a perfect number: Quote:


20030806, 19:11  #8 
Sep 2002
2×331 Posts 
ok
thanks, that accounts for the missing pairs. 
20030806, 19:28  #9  
Dec 2002
Frederick County, MD
2·5·37 Posts 
Quote:
2+8=10, 1+0=1; 4+6+9=19, 1+9=10, 1+0=1; etc. But I don't know if that statement is an "iff" statement, and if it isn't (and I don't think it is), the algorithm won't work. 

20030806, 19:31  #10 
Aug 2002
2×3×5 Posts 
Counterexample:
2^10*(2^111) = 2096128 
20030806, 19:51  #11 
Dec 2002
Frederick County, MD
2×5×37 Posts 
Actually, after looking at it, the summing the digits of a number of form 2^(2n1)  2^(n1) (This formula makes numbers of the binary form describe at the web site) I think results in 1 if n is prime. In no way could this be used to prove that a number is perfect.
BTW, 2+9+6+1+2+8 = 28, 2+8 = 10, 1+0 = 1 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Odd Perfect Number Search  Factoring Project  pinhodecarlos  Forum Feedback  1  20120911 05:11 
How to generate base10 representation of Mersenneprime perfect numbers?  James Heinrich  Miscellaneous Math  10  20120308 07:20 
How does the Odd Perfect Number search work?  jasong  Math  5  20070414 21:56 
Could a bot be used to help the Odd Perfect Number search?  jasong  Factoring  1  20070413 01:52 
How much work on Odd Perfect Number search?  jasong  GMPECM  5  20070411 03:00 