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

+-------------------------------------------------------+

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