mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-04-11, 21:29   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default How does the Odd Perfect Number search work?

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.
jasong is offline   Reply With Quote
Old 2007-04-12, 03:49   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

236110 Posts
Default

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

It's pretty easy to prove that if 34 divides N but 35 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 34 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 3606 because we don't know any factors for the sum of divisors of 3606 (which can be expressed as (3607-1)/2), so we don't know how to start the sub-argument. This is why we need factors.

William
wblipp is offline   Reply With Quote
Old 2007-04-12, 23:58   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default

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.

Last fiddled with by jasong on 2007-04-13 at 00:32
jasong is offline   Reply With Quote
Old 2007-04-13, 01:00   #4
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3·7·167 Posts
Default

Snippet gotten from a link after Googling "odd perfect number":
Quote:
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):
Quote:
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...
jasong is offline   Reply With Quote
Old 2007-04-13, 05:17   #5
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

3×787 Posts
Default

Quote:
Originally Posted by jasong View Post
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 35 is easy to dismiss because we know that the sum of the factors is (36-1)/2, and this exponent 6 factors into 2 and 3, so we know that (32-1)/2 and (33-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 32 and we would have a valid proof for 35. This idea works except when the exponent+1 is a prime, hence only those cases need to be explicitly considered.
wblipp is offline   Reply With Quote
Old 2007-04-14, 21:56   #6
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

3×7×167 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odd Perfect Number Search - Factoring Project pinhodecarlos Forum Feedback 1 2012-09-11 05:11
Could a bot be used to help the Odd Perfect Number search? jasong Factoring 1 2007-04-13 01:52
How much work on Odd Perfect Number search? jasong GMP-ECM 5 2007-04-11 03:00
Is there a simple way to track progress in Odd Perfect Number search? jasong Factoring 15 2007-03-08 02:12
Search for Mersenne primes by checking for perfect numbers dsouza123 Miscellaneous Math 33 2003-09-02 16:18

All times are UTC. The time now is 06:54.

Mon Apr 12 06:54:26 UTC 2021 up 4 days, 1:35, 1 user, load averages: 1.19, 1.48, 1.50

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.