perfect numbers 
Author Message
 perfect numbers

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

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



Wed, 19 May 1993 22:56:00 GMT  
 perfect numbers
Quote:

>/* Perfect numbers. */

...

Quote:
>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




Wed, 19 May 1993 23:13:00 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. New user need help with perfect numbers.

2. Perfect Numbers

3. Perfect Numbers

4. ASM to test Perfect Number

5. Finding perfect numbers

6. Perfect Number

7. Perfect Numbers, Complexity

8. Yet another perfect number program

9. Yet another perfect number program

10. Numbers Numbers Numbers

11. Perfect example of why subclassing can be dangerous...

12. Golf - The perfect problem to compare languages with?

 

 
Powered by phpBB® Forum Software