Path: utzoo!attcan!uunet!mcvax!enea!kth!osiris!sics.se!alf
From: alf@sics.se (Thomas Sj|land)
Newsgroups: comp.lang.prolog
Subject: Christmas pleasure.
Message-ID: <ALF.88Dec16173156@hathor.sics.se>
Date: 16 Dec 88 16:31:56 GMT
Sender: news@osiris.sics.se
Distribution: comp
Organization: Swedish Institute of Computer Science, Kista
Lines: 46

/* 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. */

/* Problem for your christmas pleasure: 
   This Prolog program can easily find the numbers 6,28,496, 
   but then it gets stuck.
   Reformulate the program so that it finds 
   more interesting perfect numbers ! 

   A knowledgeable colleague gave the following theorem:

   if (2^p-1) is a (mersenne) prime 
   then (2^p-1) * 2^(p-1) is a perfect number.

   Check it and ponder ! If you write a nice little Prolog program
   to generate such numbers, why not share it ? 
*/

divides(I,D) :- I is I//D*D.

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

divisors(I,D) :- J is I//2+1, upto(J,L), divisors(I,L,D).
divisors(I,[],[]).
divisors(I,[H|T],L) :- (divides(I,H) -> L=[H|R] ; L=R), divisors(I,T,R).

sumof(L,S) :- sumof(L,0,S).
sumof([],A,A).  
sumof([H|T],A,S) :- A1 is A+H, sumof(T,A1,S).

int(1).
int(I) :- int(I1), I is I1+1.

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


--
Thomas Sj|land
SICS, PO Box 1263, S-164 28 KISTA, SWEDEN
Tel: +46 8 752 15 42	Ttx: 812 61 54 SICS S	Fax: +46 8 751 72 30
Internet: alf@sics.se or {mcvax,munnari,ukc,unido}!enea!sics.se!alf