Path: utzoo!attcan!uunet!mcvax!inria!crin!pierron
From: pierron@crin.crin.fr (Laurent PIERRON)
Newsgroups: comp.lang.prolog
Subject: Re: perfect numbers
Message-ID: <709@crin.crin.fr>
Date: 20 Dec 88 22:56:54 GMT
Organization: CRIN, Nancy, France
Lines: 51

/* Perfect numbers. */

/* A perfect number is a number that equals the sum of its
   divisors  (excluding itself of course).  The Prolog
   program below is an inefficient but correct formulation. */*/

/* The program below is more efficient than the last program,
   the complexity is square root of N vs linear with N */

/* The major improvement is in the search of the divisors. Only
   the numbers between 2 and sqrt(N) are tested for divide. */

/* The second improvement is in the generation of integers, with
   the using of an accumulator. */

/* And a trick for the representation of the list of integers
   allow  to evaluate the sum of integers in one step. */

divides(I,D,Q) :- Q is I/D, integer(Q).

upto(N,L) :- upto(N,2,L).
upto(N,I,[I|T]) :- I<N, I1 is I+1 , upto(N,I1,T).
upto(N,I,[]) :- I>=N.

divisors(I,1+D) :- J is sqrt(I), upto(J,L), divisors(I,L,D1),
	perfect_square(J,D1,D).
divisors(I,[H|T],L) :- (divides(I,H,Q) -> L=H+Q+R ; L=R), divisors(I,T,R).
divisors(I,[],0).

perfect_square(N,D,N+D) :- integer(N).
perfect_square(N,D,D) :- not integer(N).

sumof(L,S) :- S is L.

int(N) :- int(1,N).
int(N,N).
int(A,N) :- B is A+1, int(B,N).

perfect_number(P) :- int(P), divisors(P,D), sumof(D,P).

--
+-------------------------------------------------------+
|	Laurent PIERRON					|
|							|
|	Centre de Recherche en Informatique de Nancy	|
|	Bd des Aiguillettes BP 239			|
|	54506 Vandoeuvre-les-Nancy Cedex France		|
|							|
|	Tel.: 83 91 21 40 poste 3028			|
|	e-mail: pierron@crin.crin.fr			|
+-------------------------------------------------------+