20070411, 21:29  #1 
"Jason Goatcher"
Mar 2005
3×7×167 Posts 
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. 
20070412, 03:49  #2 
"William"
May 2003
New Haven
2361_{10} Posts 
It's obvious that if N=3^{4}, then the sum of divisors of N is 1+3+9+27+81 = 121.
It's pretty easy to prove that if 3^{4} divides N but 3^{5} 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^{4} 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 factorchain 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 subargument 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 subsub 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^{606} because we don't know any factors for the sum of divisors of 3^{606} (which can be expressed as (3^{607}1)/2), so we don't know how to start the subargument. This is why we need factors. William 
20070412, 23:58  #3 
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
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 20070413 at 00:32 
20070413, 01:00  #4  
"Jason Goatcher"
Mar 2005
3·7·167 Posts 
Snippet gotten from a link after Googling "odd perfect number":
Quote:
Here's what I think it should say(change in bold): Quote:


20070413, 05:17  #5 
"William"
May 2003
New Haven
3×787 Posts 
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^{5} is easy to dismiss because we know that the sum of the factors is (3^{6}1)/2, and this exponent 6 factors into 2 and 3, so we know that (3^{2}1)/2 and (3^{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 subsub cases used for 3^{2} and we would have a valid proof for 3^{5}. This idea works except when the exponent+1 is a prime, hence only those cases need to be explicitly considered.

20070414, 21:56  #6 
"Jason Goatcher"
Mar 2005
3×7×167 Posts 
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. :) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Odd Perfect Number Search  Factoring Project  pinhodecarlos  Forum Feedback  1  20120911 05:11 
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 
Is there a simple way to track progress in Odd Perfect Number search?  jasong  Factoring  15  20070308 02:12 
Search for Mersenne primes by checking for perfect numbers  dsouza123  Miscellaneous Math  33  20030902 16:18 