alf@sics.se (Thomas Sj|land) (12/17/88)
/* 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