Path: utzoo!attcan!uunet!husc6!rutgers!gatech!udel!burdvax!pearl!lang
From: lang@pearl.PRC.Unisys.COM (Francois-Michel Lang)
Newsgroups: comp.lang.prolog
Subject: Re: perfect numbers
Message-ID: <8722@burdvax.PRC.Unisys.COM>
Date: 21 Dec 88 23:13:47 GMT
References: <709@crin.crin.fr>
Sender: news@PRC.Unisys.COM
Organization: Unisys Corporation, Paoli Research Center; Paoli, PA
Lines: 61

In article <709@crin.crin.fr> pierron@crin.crin.fr (Laurent PIERRON) writes:
>/* Perfect numbers. */
...

>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).

I'm not sure I understand what the 1+D and N+D are doing in there...

Since perfect numbers seem so popular these days,
here's another version, inspired by Arun Lakhotia's
discussion of program transformation applied to isprime/1.
This basically does for the previous versions of perfect_number/1
what Lakhotia did for his various versions of isprime/1.

Look, ma, no lists!
This version is also faster.

% ---------------------------------------------------------------------------

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

int(I) :- int(1, I).
int(N, N).
int(I, N) :-
	J is I + 1,
	int(J, N).


perfect_number(P) :-
	int(P),
	sum_of_own_divisors(P).

sum_of_own_divisors(P) :-
	Top is P // 2,
	sum_of_own_divisors(1, Top, 0, P).
sum_of_own_divisors(I, Top, SumSoFar, P) :-
	I =< Top,
	( I =:= Top ->
	  ( divides(P, Top) ->
	    P is SumSoFar + Top
	  ; P is SumSoFar
	  )
	; divides(P, I) ->
	  NextSum is SumSoFar + I,
	  J is I + 1,
	  sum_of_own_divisors(J, Top, NextSum, P)
	; J is I + 1,
	  sum_of_own_divisors(J, Top, SumSoFar, P)
	).

% ----------------------------------------------------------------------------
----------------------------------------------------------------------------
Francois-Michel Lang
Paoli Research Center, Unisys Corporation lang@prc.unisys.com (215) 648-7256
Dept of Comp & Info Science, U of PA      lang@cis.upenn.edu  (215) 898-9511