perfect numbers

[max.yevs]

I'm trying to make a perfect numbers script but having almost no success...
Perfect numbers are those whose factors add up to twice the number itself... factors don't have to be prime...

So like the first four are 6, 28, 496, 8128...
28: 1,2,4,7,14,28
1 + 2 + 4 + 7 + 14 + 28 = 56
56 = 28*2

I've made a prime numbers script, and a factorization script, but this one I just can't get right...

Here's one of the simpler ways i was trying to do it:

print ("Perfect Numbers")
a = 0
b = []
while True:
    for n in range(a+1):
        if n is not 0:
            if a % n is 0:
                b.append(n)
                m = sum(b)
                if m is 2*a:
                    print(a)
    a += 1

I've tried making lots of variations, but all the times it gives me a couple wrong numbers, i.e. 2 or 6,8 and/or just freezes... if only it could find me the first few perfect numbers...

[jlm699]

Well first problem is that you're never clearing the contents of your list b . Also, you should move the summation of b outside of the for loop so that it only happens once you've found all the factors of the desired number... That should get you pointed in the right direction.

[woooee]

You should not be using "is" for comparison. It is used to test if the objects are the same. Guido, et al decided to store an internal list of 1-256 and reference the list for those numbers, so if you try:
x=257
print x is 257
it will print False because they are different objects.

#if n is not 0:
        ## use
        if n:     ## if n != 0: will also work

            #if a % n is 0:
            if a %n != 0:

[max.yevs]

right jlm, except the whole point of the loop is testing different numbers to see if they're perfect... like testing 1, then a +=1, or 2, then 3, etc.

wooee, right but if "is" is not the same as "=", this shouldn't work:

x = 257
if x is 257:
    print x

but it does work and it gives 257... i would use "=" anyways except for some reason when i do it says syntax and highlights the "="... no such problems with others such as !=, >=, <=, etc.
"!=" means "not equal to" right?

x = 257
if x != 257:
    print x

this would return nothing...

i suppose i could do

x = 257
if x != 257:
    print x
else:
    print x

and that prints 257, but how is that better than "is"?

[jlm699]

right jlm, except the whole point of the loop is testing different numbers to see if they're perfect... like testing 1, then a +=1, or 2, then 3, etc.

My first advice to FIX your code, was to clear the contents of b when you move onto a new a since it won't have the same factors.

I understand the point of the loop, as I have your program working on my system. Do you have it working yet? Didn't think so. Maybe you misunderstood what I was suggesting. I said to move it outside of the for loop, not the while loop.

You're testing different numbers using a , which is incremented at the end of the while loop. The for loop is used to get all the factors of a and append them to b . So I suggested moving the sum(b) and subsequent perfect number check to after the for loop to save processing time.

As it stands now, every time you find a factor of a you append it to b and check to see if the contents of the array are twice the original number even though you haven't completed finding all factors.

EDIT: Oh, and when doing a comparison you have to use == , not = , as the single equals sign is for assignment.

[max.yevs]

haha, it works!
thanks you had the right idea to move it out of the 'for' loop... sorry i really did think you meant the 'while' loop...

print ("Perfect Numbers")
a = 0
while True:
    b = []
    for n in range(a+1):
        if n != 0:
            if a % n == 0:
                b.append(n)
    m = sum(b)
    del(b)
    if m is 2*a:
        print(a)
    a += 1

it only finds three numbers: 0 , 6, and 28 which is accurate because 6 and 28 are the first two numbers... after then it freezes, which is expectable because it has quite a bit to run before the next number 496...

anyways, thanks it works. and if anyone knows more efficient ways of writing this i'm interested to see it!

[adam1122]

Since you nearly had it, here's a working example with minimal changes to your code with comments where there are changes.

print ("Perfect Numbers")
a = 1 #No need to start at 0
b = []
while True:
    for n in range(1, a+1): #Start at 1 and remove the check for 0 because it won't happen
        if a % n == 0:
            b.append(n)
    m = sum(b)   # Remove some indent on these lines
    if m == 2*a: #
        print(a) #
    b = [] # Reset for next number
    a += 1

You should think about optimizations you could make. For example, there's no need to continue checking for factors past half of the number.

[max.yevs]

thanks adam, do you know any ways to optimize it? surely there has to be a better script... because given that for every number a it has to run like a 'for' loops, it takes it forever... i've had it running for 10 minutes and it still didn't get 496...

[adam1122]

It definitely shouldn't take 10 minutes. But think about the problem of the sum of the factors. I gave you one very simple optimization (don't loop through all numbers [0,a]). Try creating a program that gets the sum of the factors of a number. Make that a function and you can use it in solving this problem.

It's thinking about problems as simple parts that you can put together as a whole that makes finding solutions, bug fixing and optimizations much easier.

[max.yevs]

that is actually a very good optimization to only do it up to half the number...
it found the first three (up to 496) pretty much instantly,
and found 8128 after like three seconds...

print ("Perfect Numbers")
a = 1
b = []
while True:
    for n in range(1,((a/2)+1)):
        if n != 0:
            if a % n == 0:
                b.append(n)
    b.append(a)
    m = sum(b)
    b = []
    if m == 2*a:
        print(a)
    a += 1

anyways i'll just have to play around with it, try to put it in a seperate program or function as you suggest...

[adam1122]

if n != 0:

This is not needed. It will never be false.

[max.yevs]

oh, right i just had it left from previous attempts...

i've been thinking of another way that might make it faster: as soon as it finds n, it also finds m, the other factor of number a where m*n = a, and it only does this as long as n<m... both n and m are added to the list b...(with the exception of n = m [which will happen for square numbers], then only n is added)

so like say the number 496... it has the factors:
1,2,4,8,16,31,62,124,248,496...
so the way i had it in the last post, it would check all n up to 248...
this way it would check all n up to only 31...which might speed it up significantly

i'll post it if i can get it to work

[max.yevs]

it was actually a lot easier then i thought, instead of doing it to the point of n>m, i simply did it to the square root of a...

print ("Perfect Numbers")
a = 1
b = []
while True:
    for n in range(1,((a**.5)+1)):
        if a % n == 0:
            m = a/n
            if m == n:
                b.append(n)
            else:
                b.append(m)
                b.append(n)
    x = sum(b)
    b = []
    if x == 2*a:
        print(a)
    a += 1

it was slightly faster, instead of just finding 6, 28, and 496 instantly, it also found 8128 instantly... but it wasn't like i hoped that it would just scroll through the numbers...

[adam1122]

You could also get rid of the list and accumulate the sum in the loop. This should make it slightly faster.

[max.yevs]

like this?

print ("Perfect Numbers")
a = 1
while True:
    x = 0
    for n in range(1,((a**.5)+1)):
        if a % n == 0:
            m = a/n
            if m == n:
                x += n
            else:
                x += n + m
    if x == 2*a:
        print(a)
    a += 1

works well, of course it has to be faster, even though it still just immediately finds the first 4 numbers.... this without lists way is the way i was trying to do it originally, but when i couldn't get it to work and i thought maybe organizing into lists will help...

i really doubt theres any way to make it faster than this, its always going to have to factorize very large numbers, it would take something extremely clever...

[max.yevs]

oh, no wonder it can never find the fifth one... i just looked it up, its 33,550,336. of course 8 thousand is no problem, but 33.5 million would take forever! the tenth number is 191,561,942,608,236,107,294,793,378,084,303,638,130,997,321,548,169,216! maybe perfect numbers were not the best list to choose...

it might be quick with an algorithm, as apparently each number is (2**n)(2**(n+1) -1), but not for all n, just for some random ones...i suppose though you could first run k through that (2**k)(2**(k+1)-1) thing so that then you would have much less a's to test.

[max.yevs]

the best i've come up with is the following:
maybe using the 2**k thing is kind of losing the essence, but given that this program is extremely slow, i'm going to go ahead and use it...

print ("Perfect Numbers")
k = 0
while True:
    a = 2**(2*k+1)-2**k
    x = 0
    for n in range(1,((a**.5)+1)):
        if a % n == 0:
            m = a/n
            if m == n:
                x += n
            else:
                x += n + m
    if x == 2*a:
            print(a)
    k += 1

it will come up with 7 numbers pretty much instantly, im sure it can realistically do 10 (k = 88)... maybe if i leave it running on my computer for a couple hundred years, it would find me the 45th number, and i would have made a world discovery!