Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!mcvax!botter!klipper!victor
From: victor@cs.vu.nl (L. Victor Allis)
Newsgroups: comp.lang.pascal
Subject: Re: Perfect number program
Message-ID: <918@klipper.cs.vu.nl>
Date: Wed, 7-Oct-87 16:01:40 EDT
Article-I.D.: klipper.918
Posted: Wed Oct  7 16:01:40 1987
Date-Received: Sat, 10-Oct-87 17:41:20 EDT
References: <9652@brl-adm.ARPA>
Reply-To: victor@cs.vu.nl (Victor Allis)
Organization: VU Informatica, Amsterdam
Lines: 60

In article <9652@brl-adm.ARPA> 11SSTEIN%GALLUA.BITNET@wiscvm.wisc.EDU writes:
>
>
> I am working on a perfect number program and I have faced some problems.
>
> Notice: A perfect number is a number that has its divisors add up to itself.
> I.E. 6 = 1 + 2 + 3 = 6
>     28 = 1 + 2 + 4 + 7 + 14 = 28
>
>     All that... you have an idea on a good program?
>
>    Any ideas?

It is well known that every even perfect number must be of the form
2^(p-1) * (2^p - 1), where 2^p -1 is prime.

Since there are only a little over 30 known primes of the form 2^p - 1,
there are only 30 known perfect numbers.

There are no odd perfect numbers found so far, neither is proven that
none exist.

This gives the following suggestions:

1) Find a recent article on Mersenne primes (2^p -1), and make a list
   of the perfect numbers these primes produce. This gives a very fast
   program.
2) Start looking for odd perfect numbers. This probably will not produce
   any perfect numbers, but could make you famous if you find one.
3) If you just want search for perfect numbers between, say, 1 and
   100000, for fun, you could try something like the following:

--------------
program Perfect(input, output);

const Max         = 100000;
var   Numbers     : array[1..Max] of integer;
      i, j        : integer;

begin
  for i := 2 to Max do
    Numbers[i] := 1;
  for i := 2 to Max do
    for j := 2 to Max div i do
      Numbers[i*j] := Numbers[i*j] + i;
  for i := 1 to Max do
    if Numbers[i] = i then
      writeln(i:1, ' is a perfect number.')
end.
--------------

This program produced all perfect numbers between 1 and 100000 in 64
sec. on our VAX-11/70
Its complexity is O(n*logn).

I hope this helped.

Victor Allis.
Free University of Amsterdam.
The Netherlands.