More Perfect Numbers

Mathochist (What’s the story on perfect numbers? correctly states that “given a Mersenne prime, applying the formula will always give a perfect number” but he takes the word of the questioner, Mac McCartney, that there are only 38 known perfect numbers. The 42nd Mersenne Prime was found last February, so we know of at least 42 perfect numbers. The 41st was found in May, 2004, and there may be more by now.

Mathochist also writes that:

It may help those who don’t know math to realize that finding a Mersenne prime is not an easy task when the numbers grow as large as seven million digits. So while we can generate perfect numbers from Mersenne primes, the latter aren’t thick on the ground. That’s what’s really holding back the search.

Also, on the subject of odd perfect numbers, it is easy to find odd abundant numbers, where the sum of the factors is greater than the number itself (e.g., 945, which is 3^3 x 5 x 7, so it’s sum is 975), or odd deficient numbers (3, 5, 7, all of whose sums are 1; or 9 whose sum is 4), but no one has ever found an odd number whose sum of factors is the number itself. Anyone who ever found such an odd perfect number would be famous.

I just wanted to throw that out, in case there were any geocentrists reading this, with time on their hands.



Sorry, I should have googled for a link.

I know who the geocentrists are, but what on earth do they have to do with perfect numbers?

I just meant, they might find it diverting. For a few years.

In any case, I want to thank Mathochist for another wonderful guest Staff Report! Not all mathematicians can express concepts for non-mathematicians to unnerstand, and I think Mathochist has done a fantastic job here.

A thought: Could perfect numbers be used as part of the prime-testing process for Merseinnes? As in: You have a number of the form 2[sup]n[/sup] - 1, and you want to know it’s prime. n is of course prime (this is a well-known necessary condition for Merseinne primes). Now, if 2[sup]n[/sup]-1 is a true Merseinne prime, then there’s an associated perfect number 2[sup]n-1[/sup](2[sup]n[/sup] - 1). Again assuming that our starting number is prime, it’s very easy to find all of the factors of this potential perfect number. Add up these known factors, and see if they add up to the potential perfect. If they do, well, you still don’t know if your original number was prime, but if they don’t, then you can be sure it wasn’t. Is this a practical test?

Maybe, but probably not. There are some very fast and highly accurate tests for primality, and factoring is slow. Now, if you show us a quick way to factor, we’re talking something interesting…

Strike that. 2[sup]n - 1[/sup] only has at less bit than 2[sup]n[/sup] - 1, so if you can factor the former quickly, you can just factor the latter almost as quickly.

No, it’s not practical.

We know that the sum of all the easy to find factors is equal to the number.

For a given number whose prime factorization is A^a x B^b x C^c x …, where A, B, C are unique primes, then the sum of all its factors is (A^a + A^(a-1) + … + A + 1) x (B^b +…) x (C^c + …) x …

The sum of all the factors of 2[sup]n-1[/sup](2[sup]n[/sup] - 1) where the factors are a power of two, or powers of two times (2[sup]n[/sup] - 1), is 2[sup]n-1[/sup](2[sup]n[/sup] - 1) regardless of whether (2[sup]n[/sup] - 1) is prime or not.

I can factor 2[sup]n - 1[/sup] very quickly! :slight_smile:

It’s 2 times 2[sup]n - 2[/sup]

Ah. I should have realized that. And in fact that’s probably a big chunk of Euler’s proof, isn’t it?

Yes, the rest of it is proving that all even perfect numbers have that form.


Anyway, the point is this: something would have to be very unusual for the running time of a general purpose factorization to depend on anything other than the number of bits in its input, so it’s going to be faster to just factor 2[sup]n[/sup] - 1 than to factor 2[sup]n - 1[/sup](2[sup]n[/sup] - 1).

btw, in binary, 2[sup]n - 1[/sup] is 10[sup]n - 2[/sup], while 2[sup]n[/sup] - 1 is 1[sup]n - 1[/sup]. That’s the same number of bits (despite what I said earlier).

Well, also as I stated nobody but hobbyists are really doing much searching. Despite a lot of people hearing about them as young students (since the condition can be stated so simply), perfect numbers just aren’t really good for anything.

Incidentally, I’m still waiting to see if anyone finds the hidden joke. Dex, no telling :smiley:

Yeah, I’ve got a LISP program (of all the languages I have, it does big-precision arithmetic fastest) which gets the first 15 in a couple of seconds and the next 5 in a few minutes, but to get much beyond that you have to dedicate a supercomputer.

Actually, now that I’ve looked at the final result of my work, it seems that the joke was so carefully crafted and hidden that it’s been edited out!

No, general purpose factoring, when the input is a string of binary zeroes, would always truncate the trailing zeroes. The factors of two are easy to ignore.

You must have left something out. Of the four numerals, the first three include the digit two so they’re not binary, and the last one is always 1, no matter what base, or what n equals.

string of binary digits :smack: