Conference rusure::math

        It doesn't mean add up all of the prime divisors, with or
        without duplicates.  It means add up all of the (positive
        integral) divisors, except for the number itself (the
        arguments for and against this exception are a can of
        worms that I shall merely allude to but not open).
        
        220 = 2 * 2 * 5 * 11 is divisible by 1, 2, 4, 5, 10, 11,
        20, 22, 44, 55, 110, and 220.  The sum of all of these
        (except 220) is 284.
        
        284 = 2 * 2 * 71 is divisible by 1, 2, 4, 71, 142, and
        284.  The sum of all of these (except 284) is 220.
        
        If p1, ..., pk are distinct primes, then the sum of all
        of the positive integral divisors of N = p1^e1 * ... * pk^ek
        (including N itself) is
        
        (1 + p1 + ... + p1^e1) * ... * (1 + pk + ... + pk^ek)
        = ((p1^(e1+1) - 1) / (p1 - 1)) * ... * ((pk^(ek+1) -1) / (pk - 1))
        
        For 220 = 2^2 * 5 * 11 this is (1+2+4)(1+5)(1+11)
        = 7 * 6 * 12 = 504 = 284 + 220.
        
        Dan
        

    I recall reading about a generalization of this.
    
    	Let �(N) = sum of divisors of N (not including N itself)
    
    So a pair of numbers, N and M, are said to be amicable if
    
    	�(N) = M and �(M) = N
    
    Are there three numbers, N, M and L, such that the following holds?
    
    	�(N) = M, �(M) = L and �(L) = N
    
    Is there a longer sequence of numbers with this quality?  If memory
    serves, I believe an example of six numbers was given.  I shall endeavor
    to find the source and report back.

    I believe there is a sequence of 5 in the 5-digit range, and a longer
    sequence of 30 or so up in the 10-digit range.  I don't know of any 
    ODD amicable (or perfect) numbers.
    
    A convenient algorithm to try is to select an even number x1 and
    calculate x2 = �(x1) and x3 = �(x2) and so on, giving up when you
    hit an odd number.  Otherwise, keep track of all the xN and compare
    each new total to the whole list.  Eventually you'll "hit", finding
    a number already in the list.  Often you'll just rediscover 220/284
    or another known chain, but who knows -- with a bignum package you might
    make a new discovery!
    
    It's also an interesting programming project for teaching arrays,
    especially if you have to form and maintain a master list of all the
    amicable chains, with no duplication.
    
      John

I don't understand your arithmetic.

Run this basic program:

10 rem n = one of an amicable number pair
20 input n
50 sum = 0
70 print "Here are the divisors:"
100 for k=1 to int(n/2)+1
200 if n/k-int(n/k) >= 1e-6 then 500
300 print k,
400 sum=sum+k
500 next k
600 print
700 print "Sum = ";sum

        re .4,
        
>> I don't understand your arithmetic.
        
        a)  The two prime factorizations were switched.
        
        b)  The sum of prime divisors was taken, with each prime
        added in as many times as it occurs in the prime
        factorization, e.g., 284 = 2x2x71 => 2+2+71 for the sum.
        Sort of a global replace of "+" for "x".  It's a function
        and it's understandable, it's just not what is wanted for
        amicable numbers.
        
        Dan

    I started to write a program to look for cycles in amicable numbers, and
    discovered that I already had such a thing!  See the results below.
    Note the 5-cycle that starts with 12496, and the 28-cycle (!) starting
    with 376736, and a few large 4-cycles it happened to stumble across.

6 -> 6

28 -> 28

220 -> 284,220
496 -> 496

1184 -> 1210,1184
2924 -> 2620,2924
5020 -> 5564,5020
6232 -> 6368,6232
8128 -> 8128

10744 -> 10856,10744
12285 -> 14595,12285
12496 -> 14288,15472,14536,14264,12496
17296 -> 18416,17296

66928 -> 66992,66928
67095 -> 71145,67095
69615 -> 87633,69615
76084 -> 63020,76084
79750 -> 88730,79750

100485 -> 124155,100485
122265 -> 139815,122265
122368 -> 123152,122368
141664 -> 153176,141664
142310 -> 168730,142310
171856 -> 176336,171856
176272 -> 180848,176272
185368 -> 203432,185368
196724 -> 202444,196724
280540 -> 365084,280540
308620 -> 389924,308620
319550 -> 430402,319550
356408 -> 399592,356408
376736 -> 381028,285778,152990,122410,97946,48976,45946,22976,22744,19916,
	  17716,14316,19116,31704,47616,83328,177792,295488,629072,589786,
	  294896,358336,418904,366556,274924,275444,243760,376736
455344 -> 437456,455344
469028 -> 486178,469028
503056 -> 514736,503056
522405 -> 525915,522405
600392 -> 669688,600392
609928 -> 686072,609928
624184 -> 691256,624184
635624 -> 712216,635624
643336 -> 652664,643336
667964 -> 783556,667964
726104 -> 796696,726104
802725 -> 863835,802725
879712 -> 901424,879712
898216 -> 980984,898216
947835 -> 1125765,947835
998104 -> 1043096,998104

1264460 -> 1547860,1727636,1305184,1264460
2115324 -> 3317740,3649556,2797612,2115324
2723792 -> 2874064,2723792
2874064 -> 2723792,2874064
4314616 -> 4238984,4314616
4532710 -> 6135962,4532710

438452624 -> 445419376,438452624

        In my office dictionary "amicable" is listed as
        meaning "adj. Friendly; peaceable."  So some
        numbers are friendly, like 220,284; and some are
        downright gregarious, like 12496,14288,15472,14536,14264.
        
        But then we get standoffish numbers like 6.  24.  496.
        Stuck up.  Snobs.  Yuppies.  You know the type.  I wonder
        what we should call these numbers?
        
        Dan

RE: .7 (Dan)

    "Amicable singles" are generally known as "Perfect Numbers".  There is
    a long history of their study, and amicable pairs, etc. were developed
    as a generalization of perfect numbers.  Perfect numbers have many
    interesting properties (e.g., the sum of the multiplicative inverses of
    *all* the factors of a perfect number -- including the number itself --
    always equals 2), and many unsolved problems concerning them (e.g., is
    there an odd perfect number?).

					Topher

    ref .7 (Dan)
    >    But then we get standoffish numbers like 6.  24.  496.
    >    Stuck up.  Snobs.  Yuppies.  You know the type.  I wonder
    
    Iam soory Dan, i dont understand, why do you say these numbers were 
    snobs ? is that in general, or in certine context?
    
    i thought one (i.e. a number) has to be at least an odd to qualify, and 
    a prime to be a definite Snob. in general. yes ?
    
    496 in particular shounds like a nice number.
    
    regards,
    /nasser
    
    

        It was a joke.  I wanted to say nasty things about them
        then ask for a name, so someone could reply "Let's call
        them PERFECT numbers! :-)". (Which as .8 said is what
        they are called.)  I thought it would be mildly amusing.
        
        DAN

    So much for my theory about "no odd amicable numbers".  That has been
    replaced with a conjecture that "odd amicable numbers are always
    multiples of 5".
    
    Peter, have you exhausted all 2^31 possibilities yet?
    
      John

> Peter, have you exhausted all 2^31 possibilities yet?

I became exhausted before the numbers did.  :^)

The program is fairly fast, but also fairly brute-force.  It checked up to a
million in about ten minutes.  At that rate, 2^31 numbers would take 15 days.
And it handles longword overflow by merely advancing to the next number.

Uh, 24 is not perfect.  28 is perfect.  Perfect numbers always have a bunch
of 1's, then a bunch of exactly one less as many 0's, when written in binary.
For example

	6 = 110
       28 = 11100
      496 = 111110000

Remember, perfect numbers are those whose factors add to themselves, for
example

	28 = 1 * 2 * 4 * 7 * 14

Another way of writing the binary pattern thing is that perfect numbers
are of the form


	 n-1    n
	2   * (2 - 1)


I've always liked that formula because it's "2 to the n minus 1 times 2 
to the n minus 1" and I never have to remember where the parentheses are,
since they're both places !

/Eric

        Transcription error typing in numbers from the previous reply. :-)
        
        Dan

    re .13
    
    Your statements about perfect numbers only apply to *even* perfect
    numbers.

    Re .15:
    
    I bet you can't prove that!
    
    
    				-- edp

        A perfect number that was not even would be very odd.
        
        Dan

RE: .16 (edp)

>    I bet you can't prove that!

    Which was in regards to .15 (GARSON)

>    Your statements about perfect numbers only apply to *even* perfect
>    numbers.

    Which in turn was in regards to .13 (Eric), among other things:

>	 n-1    n
>	2   * (2 - 1)

    Although it would be rather difficult to come up with an example of an
    odd perfect number which violated the above formula, its not at all
    difficult to prove that: "no odd perfect number has the above form".
    What I would be *very* impressed by is a proof of Eric's statement,
    since that would amount to a proof of a widely studies, unproven
    conjecture.

					    Topher

    Re .18:
    
    > -< I'll gladly take your money! >-

    Okay, but my money buys me all publication rights!
    
    > . . . its not at all difficult to prove that: "no odd perfect number
    > has the above form".
    
    See, you're halfway there already.  Where's the other half?
    
    
    				-- edp

RE: .19 (edp)

    Maybe I'm missing something, but *what* other half?

    The proof that all even perfect numbers have the form that Eric
    mentioned goes back to Euler, and has, as I remember, a pretty simple
    proof.  Euler actually proved a stronger result that an even number
    is perfect iff it has that form and (2^n)-1 is prime (hence there is
    a one-to-one correspondence between even-perfects and Mersenne primes).

    As I read it, the claim (that Eric's statements only apply to even
    perfect numbers) does not rest on the existence of odd perfect numbers,
    so that does not need to be proven.

					Topher

re .20
    
    Since I started this rathole, I'll just try and clear it up.
    
>    As I read it, the claim (that Eric's statements only apply to even
>    perfect numbers) does not rest on the existence of odd perfect numbers,
>    so that does not need to be proven.
    
    In .13 it said
    
>>  Perfect numbers always have a bunch of 1's, then a bunch of exactly one
>>  less as many 0's, when written in binary.
    
    Clearly if there exists an odd perfect number then the statement in .13
    is false because this binary pattern obviously produces only even
    numbers AND thus in this case my nit is correct. I don't think anyone
    is unclear about this aspect.
    
    On the other hand, if there are no odd perfect numbers then the
    statement in .13 is completely correct. This begs the question as to
    whether my statement is correct in this case. I believe this is not a
    mathematical question - but a semantic one. The phrase "only apply to even
    perfect numbers" suggests to me two things viz.
    
    1. apply to even perfect numbers.
    2. do not apply to odd perfect numbers.
    
    Can a statement apply or not apply to something that doesn't exist? I
    don't think this question has an answer.
    
    In retrospect, my claim was sloppily worded.
    
    Yes, I may have been out-nitted here. :-)

    Oh and by the way I have discovered a truly wonderful proof of the
    non-existence of odd perfect numbers but there isn't time to post it
    before the network link goes away.

    Re .21:
    
    As .21 indicates, the other half is to prove there is an odd perfect
    number.  Otherwise, the statement "Each odd perfect number is of the
    form (2^m-1)*2^n." is true, and therefore the statement "Each perfect
    number is of the form (2^m-1)*2^n." is true; the restriction for odd
    numbers would not be necessary.
    
    
    				-- edp

	An odd perfect number would have to be a prime times a square.

Andrew.

>> .23  
>>			-< trivial observation >-
>> An odd perfect number would have to be a prime times a square.
        
        From .1, if N = p1^e1 * ... * pk^ek (where p1,...,pk are
        distinct primes) then the sum of the divisors of N is
        (1 + p1 + ... + p1^e1) * ... * (1 + pk + ... + pk^ek)
        = ((p1^(e1+1) - 1) / (p1 - 1)) * ... * ((pk^(ek+1) -1) / (pk - 1))
        
        N is perfect if this sum is equal to 2N.
        
        If N is odd, then all of p1,...,pk are odd, and each of
        the (1 + pj + ... + pj^ej) is even for odd ej and odd for
        even ej.  For odd N, there is only one factor of 2 in 2N
        and so all but exactly one of the ej must be even.
        
        Dan

RE: .21 (GARSON), .22 (edp)

    We are arguing over a matter of semantics, but I am going to stick
    to my guns.  The original phrasing was *misleading* since it appeared
    to imply that odd perfect numbers do in fact exist, but I do not think
    that it requires that an odd perfect number exists to be true.

>    As .21 indicates, the other half is to prove there is an odd perfect
>    number.  Otherwise, the statement "Each odd perfect number is of the
>    form (2^m-1)*2^n." is true, and therefore the statement "Each perfect
>    number is of the form (2^m-1)*2^n." is true; the restriction for odd
>    numbers would not be necessary.

    Obviously, if there are no odd perfect numbers than it is unnecessary
    to restrict *any* statement about perfect numbers to even perfect
    numbers.  You seem to want to translate "only even perfect numbers are
    of form F" as "It is not true that all perfect numbers have form F",
    but that is not what the original statement says -- that is an
    *implication* of the statement if there are odd perfect numbers.
    I would say that an accurate expansion of the original is "if p is a
    perfect number than p has form F only if it is even."  That does not
    depend on whether or not you can prove that there is a p which is not
    even.

    Would you really say that "Only *even* perfect numbers are even" is
    incorrect if there are no odd perfect numbers?

    This is an example of what I believe semanticists (field of
    linguistics, not mathematics) call "implicit hypotheticals".  They are
    not uncommon in natural language, and they are not generally considered
    indeterminant -- though they have "when did you stop beating your
    spouse" problems if the implied hypothetical is not clearly enough
    implied.  So for example, I might say in the UFOS conference "According
    to our knowledge of genetics, its very likely that terrestrials are
    only able to interbreed with terrestrials."  That is a legitimate
    statement, which I could go about backing up, without first having to
    provide evidence that extraterrestrials exist.

				Topher

    The Encyclopedic Dictionary of Mathematics, of the Mathematical
    Society of Japan, published in English by MIT press, 2nd English
    edition (translatio of the 3rd Japanese edition; c 1985) lists the
    following properties proven for any hypothetical odd perfect numbers:

    They must be of the form:

	      4l+1       2a[1]       2a[2]	      2a[t]
	(4k+1)	  * f[1]      * f[2]	  * ... * f[t]

    Where all the f's are odd.  Furthermore t must be at least 7.

    There are no odd perfect numbers less than 10^50.  Also "Many necessary
    conditions for an odd number to be pefect have been given and
    repeatedly improved."

				    Topher

    Eric Osman has pointed out that the description he gave previously is
    actually described by the formula (2^n-1)*2^n, which is more strict
    (and better) than the formula I gave in .22, (2^m-1)*2^n.
    
    
    				-- edp

Innocent question: is 1 a perfect number?

It conforms to the definition of being equal to the sum of its divisors.

It also conforms to the formula given in .27, (2^n-1)+2^n with n=0.


Peter

re .27
    
>    Eric Osman has pointed out that the description he gave previously is
>    actually described by the formula (2^n-1)*2^n, which is more strict
>    (and better) than the formula I gave in .22, (2^m-1)*2^n.
    
    Except that the formula (2^n-1)*2^n is wrong. The correct formula as
    stated in .13 is
    
     n-1    n
    2   . (2  - 1)
    
    which includes all even perfect numbers but many non-perfect numbers.
    
                    n
    Restricted to (2  - 1) being prime (called a Mersenne prime) this
    formula gives all even perfect numbers and only even perfect numbers.
    (But see below concerning the case n=1.)
    
    (2^m-1)*2^n includes all even perfect numbers but many non-perfect
    numbers because it ignores the connection between n & m as well as the
    condition that (2^m-1) be prime.
    
re .28
    
>Innocent question: is 1 a perfect number?
>
>It conforms to the definition of being equal to the sum of its divisors.
>
>It also conforms to the formula given in .27, (2^n-1)+2^n with n=0.

    Allowing for the change to the formula, this is still a valid question
    viz. put n=1 in the correct formula.
    
    It might on depend on the definition used but my answer would be "No".
    
    e.g. with n=1 (2^n-1) is 1 which is not usually considered prime and
    thus the above formula doesn't apply.
    
    Alternately referring to .1, it says sum the divisors excluding the
    number itself. Since the only divisor of 1 is 1, there are no remaining
    divisors to sum so the sum could be taken as 0 in which case the sum is
    not the number itself.
    
    Alternately evaluate the formula given in .1. This gives 1 which
    must equal twice the original number for the number to be perfect.
    Again this leads to the conclusion that 1 is not perfect (but then
    neither am I).