pierron@crin.crin.fr (Laurent PIERRON) (12/21/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. */*/ /* 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 | | e-mail: pierron@crin.crin.fr | +-------------------------------------------------------+
lang@pearl.PRC.Unisys.COM (Francois-Michel Lang) (12/22/88)
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
dale@linc.cis.upenn.edu (Dale Miller) (01/12/89)
The following results are known about perfect numbers. Theorem: An even number is perfect if and only if it is of the form 2^n*(2^(n+1) - 1) where (2^(n+1) - 1) is a prime (such primes are called Mersenne primes). No odd perfect numbers are known. There is the following result, however. Theorem: If an odd number is perfect, it must have at least four distinct prime factors and be larger than 2,000,000. This result has been strengthen greatly in recent years (more prime factors would need to be present and the lower bound has been raised considerably) but I don't remember the exact results. If your Prolog program happens to find an odd perfect number, be sure to publish it!