How does the Odd Perfect Number search work?

[jasong]

I understand the thrust of what the ecm client does, if not the algorithms themselves. I'm wondering if there's somewhere I can go to explore the OPN search from the beginning. Maybe someone could write out proof that no OPN exists with less than 4 digits. I feel like I've entered a play after the first Act is already finished in terms of understanding how things work.

One thing I need to mention: I've never been taught how the sigma symbol works, so that may throw a wrench into the explanation. I'm sure it's very simple, but my education was rudely cut short at the beginning of the 11th grade by mental illness, so there's a ton of stuff I have the brains to know, but have never been taught.

[wblipp]

It's obvious that if N=3⁴, then the sum of divisors of N is 1+3+9+27+81 = 121.

It's pretty easy to prove that if 3⁴ divides N but 3⁵ does not divide N, then 121 divides the sum of the divisors of N.

We know the sum of the divisors N = 2 * N,

So we know that if 3⁴ is the highest power of 3 the divides N, then 121 divides the left side of this equation. But if 121 divides the left side, it must also divide the right side, and hence 11 must divide N.

The same thing is true if you replace the 3 with any prime and if you replace the 4 with any power.

This leads to the factor-chain approach for proving that any odd perfect number divisible by 3 must be larger than some threshold. We start by saying 3 must occur to some highest power. We will sequentially suppose this highest power is 1, 2, 3, 4, 5, ...

It can't be "1" because then 4 divides the left side, which forces N to be even on the right side.

When we get to the fourth power, we observe that 11 must divide N, and we start a sub argument that "suppose the highest power of 11 is 1, 2, 3, 4 ....

Eventually we can close off the whole sub-argument because "if the power of 11 is "m" or higher, then N is too big". which allows us to drop back to considering the possible powers of 3. Often we will first need to consider sub-sub and deeper arguments with additional primes from the assumed divisors. Eventually we have eliminated all the sub cases (or we have found an odd perfect number).

I will refer you the BCR papers for how you can combine these lemmas of the form that "any odd perfect number divisible by p must exceed 10^x" to conclude that any odd perfect number must exceed 10^x.

Right now, this approach gets stuck when we want to assume the highest power of 3 is 3⁶⁰⁶ because we don't know any factors for the sum of divisors of 3⁶⁰⁶ (which can be expressed as (3⁶⁰⁷-1)/2), so we don't know how to start the sub-argument. This is why we need factors.

William

[jasong]

I'm going to do some paper and pencil work, and maybe post it. Hopefully, someone can tell me whether my starting from scratch approach is simply a less advanced version of wblipp's.

Also, could someone explain(I hope I'm giving enough information for you to know what I'm talking about) the significance of using a prime power or one less than a prime power in the search? I didn't understand the reference, so it's kind of hard for me to ask the question, I'm hoping someone who's familiar with the OPN search can figure out what I'm talking about.

Edit: Further review indicates I have a TON to learn.

[jasong]

Snippet gotten from a link after Googling "odd perfect number":

To this day, it is not known if any odd perfect numbers exist, although numbers up to 10^(300) have been checked without success...

The way that quote is phrased, someone somewhere must be hiding a supercomputer. Let's see, if we can disqualify a range of a googol every second, that would be 10^200 seconds. If we assume the universe will completely die in 10^15 years, that's 3.1536E122, so you would have to have this universe reproduced about 3.171E78 times in succession to brute force it.

Here's what I think it should say(change in bold):

To this day, it is not known if any odd perfect numbers exist, although numbers up to 10^(300) have been eliminated through mathematically logical means without success...

[wblipp]

Originally Posted by jasong

the significance of using ... one less than a prime power in the search?

Remember that we started by assuming that 3 divides the OPN, and then by sequentially assuming that the highest power of 3 is 1, 2, 3, 4, 5, .... . The case of 3⁵ is easy to dismiss because we know that the sum of the factors is (3⁶-1)/2, and this exponent 6 factors into 2 and 3, so we know that (3²-1)/2 and (3³-1)/2 are divisors of this. But we considered these terms earlier, when we were considering the possibility that the highest power of 3 was 1 or 2. Even a careless researcher will note that this previous work means that there are factors available to build a factor chain. But a careful researcher will also note that when we considered the case of "the maximum power of 3 is 2" we really proved something stonger. We could copy and paste the entire set of sub-sub cases used for 3² and we would have a valid proof for 3⁵. This idea works except when the exponent+1 is a prime, hence only those cases need to be explicitly considered.

[jasong]

I have a lot of free time. Maybe in a month or two, after I've really begun to understand everything about the OPN search(too confident, maybe?), I might try to come up with a web page or something in an attempt to make things easier.

I still have a lot to learn, though. :)