Welcome, guest | Sign In | My Account | Store | Cart

A perfect number is a number whose factors, including the number itself, sum up to twice the number. For example,6 is a perfect number since its factors (1, 2, 3, 6) sum up to 12.

Python, 17 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# Filename: perfect.py
a = True
n = 0
while a == True:                           #  To loop the following commands 
    running = True
    while running == True:
        r = 0
        n =  n+ 1
        for x in range(1,n + 1):
            if n%x == 0:                   #  To determine the factors of n
                r = r + x
                if x == n:
                    if  r == 2*n:
                        print n
                        running = False
                    else:
                        running = False
                        
                                 
            
            

I got the idea for writing a program to generate perfect numbers from a website which had posted the problem of generating them as a challenge. I took up the challenge and decided to write a program in Python to accomplish that.Solutions for the problem in other languages are there on the page, but nobody had posted a solution in Python.

9 comments

Aditya Gopalakrishnan (author) 16 years, 4 months ago  # | flag

Here's the aforementioned url: http://code.box.sk/

Markus Weihs 16 years, 4 months ago  # | flag

Hi!

Here's a slightly shorter version ;)

n = 1
while True:
    factors = [1]
    [factors.append(i) for i in range(2,n+1) if n%i == 0]
    if sum(factors) == 2*n: print n
    n += 1

Regards, Markus

Markus Weihs 16 years, 4 months ago  # | flag

Even shorter :)

n = 1
while True:
    if sum([i for i in range(1,n+1) if n%i == 0]) == 2*n: print n
    n += 1
Aditya Gopalakrishnan (author) 16 years, 4 months ago  # | flag

Thanks Markus! I'm new to python (and programming), and your solutions have taught me a lot about economy and style in writing code. Any further suggestions would be equally welcome. :) Regards, Aditya

Aditya Gopalakrishnan (author) 16 years, 4 months ago  # | flag

Thanks Markus! I'm new to Python (and programming) and your solutions have taught me a lot about economy and style in writing code. Any further suggestions about style will be equally welcome. :) Regards, Aditya

Raymond Hettinger 16 years, 4 months ago  # | flag

For-loops simplify the code.

for c in xrange(1, 100000):
    if sum(x for x in xrange(1,c) if not c%x) == c:
        print c
Steven James 16 years, 4 months ago  # | flag

Optimization. The following runs a lot faster, at the cost of some typing. (Finding perfect numbers with python is going to be slow no matter what, so I suppose it is a silly problem to optimize).

Mainly--you only need to search factors up to the square root of n.

from math import sqrt
import sys

try:
    max_n=int(sys.argv[-1])
except ValueError:
    max_n=50000

def factor(n):
    sr=int(sqrt(n)+1)
    factors=[i for i in xrange(2,sr) if n%i==0]
    factors.extend([n/i for i in factors][::-1])
    return factors

def perfect():
    print [n for n in xrange(1,max_n) if sum(factor(n))==n-1]
Andrew Dalke 16 years, 4 months ago  # | flag

precomputed values. As with just about anything dealing with primes, the fastest way to generate values is to start with precomputed values. In this case the perfect numbers can be generated from Mersenne primes, and there are only 42 or so of those which are known. Testing Mersenne candidates is faster than the general prime factor generation algorithms shown here so if you don't want to stop with a ValueError you might want to implement one of them instead, or use a service which connects to the Great Mersenne Prime Search server.

mersenne_prime_powers = [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521,
                   607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937,
                   21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
                   1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011,
                   24036583, 25964951]

def perfect_numbers():
    for p in mersenne_prime_powers:
        yield (2**p-1)*(2**(p-1))
    yield ValueError, "that's a large number"

for p in perfect_numbers():
    print p

More details at http://mathworld.wolfram.com/PerfectNumber.html .

Andrew Dalke 16 years, 4 months ago  # | flag

yield -> raise. Err, change that "yield ValueError," into a "raise ValueError,". As you might guess, I didn't make it that far in my testing. :)

Created by Aditya Gopalakrishnan on Sun, 17 Jul 2005 (PSF)
Python recipes (4591)
Aditya Gopalakrishnan's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks