Search for Mersenne primes by checking for perfect numbers

[dsouza123]

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 !

[NickGlover]

I think you missed something from that page:

Theorem One: k is an even perfect number if and only if it has the form 2^(n-1)(2^n-1) and 2^n-1 is prime.

This basically says that all mersenne primes correspond with an even perfect number and all even perfect numbers correspond with a mersenne prime.

As far as I know, an LL test is much faster than any methods we have for finding perfect numbers.

[dsouza123]

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 ?

[NickGlover]

Originally Posted by dsouza123

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 ?

You need to match the mersenne primes, not just the exponents:

2*(2^2-1) = 6
4*(2^3-1) = 28
16*(2^5-1) = 496
.
.
.

[eepiccolo]

Originally Posted by dsouza123

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 ?

You're looking at the exponents, not the Mersenne primes themselves.
The first Mersenne prime is 3 (2^2-1)
The second Mersenne prime is 7 (2^3-1)
The third Mersenne prime is 31 (2^5-1)
etc.

And these numbers are what you are matching up.

edit: Oops, Nick beat me to it.

[toferc]

Originally Posted by NickGlover

n = 2: 2^1 * (2^2-1) = 6
n = 3: 2^2 * (2^3-1) = 28
n = 5: 2^4 * (2^5-1) = 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^n-1 to see if it is prime in order to determine if 2^(n-1)(2^n-1) is perfect.

edit: oops, Nick and eepiccolo beat me to it

[NickGlover]

From the fact that even perfect numbers are of the form 2^(n-1)*(2^n-1), the binary representation must be n 1's followed by n-1 0's.

I also do not understand your algorithm for checking if a number is a perfect number:

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.

How can you get 1 from summing the digits of a large number unless you sum them mod some other number (10?)? And how does the fact that they add up to 1 mean the number is a perfect number? How do the digits of 6 and 28 add up to 1?

[dsouza123]

ok

thanks, that accounts for the missing pairs.

[eepiccolo]

Originally Posted by NickGlover

How can you get 1 from summing the digits of a large number unless you sum them mod some other number (10?)? And how does the fact that they add up to 1 mean the number is a perfect number? How do the digits of 6 and 28 add up to 1?

Other than 6, repeatedly summing the digits of a perfect number will eventually get you to 1.
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.

[toferc]

Counterexample:
2^10*(2^11-1) = 2096128

[eepiccolo]

Actually, after looking at it, the summing the digits of a number of form 2^(2n-1) - 2^(n-1) (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