Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

  • Congratulations strongm on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

generate all perfect numbers until 100. ...

Status
Not open for further replies.

nn987

Programmer
Feb 4, 2006
37
GB
Someone asked how to calculate the perfect numbers until 100 .And know I don't find that person. But here it is

%generate all perfect number until 100...
%Create perfect numbers

%divisible(10,2).
divisible(X,Y):- N is Y*Y,N =< X,X mod Y =:= 0.
divisible(X,Y):- Y < X, Y1 is Y + 1, divisible(X,Y1).


%isprime([3],Z).
isprime([X|_],X):-Y is 2, X >1, \+divisible(X,Y).
isprime([_|T],Z):-isprime(T,Z).


%Calculate the power of one number
%ie power(2,10,R)
power(_,0,1):-!.
power(N,K,R):-K1 is K-1,
power(N,K1,R1),
R is R1*N.


%formula of perfect numbers 2^(p-1)*(2^p-1)
%ie calc(2,10,R)
calc(2,K,R):power(2,K,X),R1 is X-1,
power(2,K-1,R2),
R is R1 * R2.

%using lists
%ie calc([2,3,4],R).
listperf([K|_],R):-calc(2,K,R).
listperf([_|T],Z):-listperf(T,Z).


%generate one list of N numbers.
%genList(10,L).
generateList(0,[]).
generateList(N,[X|Xs]):- N > 0,
X is N+1,
N1 is N-1,generateList(N1,Xs).


%list of N perfect numbers
%perfect(100,C)
perfect(N,C):-generateList(N,R),findall(L,isprime(R,L),P),listperf(P,C).
 
Your code is false :
C = 35184367894528 ;
C = 137438691328 ;
C = 8589869056 ;
C = 33550336 ;
C = 2096128 ;
C = 8128 ;
C = 496 ;
C = 28 ;
C = 6 ;
see here
I think that the person who wanted to calculate perfect numbers until 100 was waiting for something like that :
Code:
perfect(N, L) :-
	numlist(2, N, L1),
	include(perfect, L1, L).


perfect(N) :-
	divisors(N, 2, [1], L),
	sumlist(L, N).


divisors(N, D, LC, LF) :-
	0 is N mod D,
	!,
	D1 is D + 1,
	X is N / D,
	(   X >= D -> divisors(N, D1, [X, D |LC], LF); LC = LF).

divisors(N, D, LC, LF) :-
	X is N / D,
	(   X > D -> D1 is D + 1, divisors(N, D1, LC, LF); LF = LC).
This code use the definition of perfect numbers, it works for small numbers, for big numbers, I don't know if there is better algorithm.
 
thanks

yes
I have one error on the first part of this formula

I need to check, not only that p is prime,but that 2^p-1 is also prime(first part of the formula).

 
correction of last program.
This program need to improve performance with a prime numbers test faster.

%----------------
%Find perfect numbers


hasFactor(_,0):-!,fail.
hasFactor(N,L):-L<N,N mod L=:=0.
hasFactor(N,L):-L<N,L2 is L+1,hasFactor(N,L2).


%test of prime number
%isprime([3],Z).
isprime([X|_],X):-Y is 2, X >1, \+hasFactor(X,Y).
isprime([_|T],Z):-isprime(T,Z).


%multiply with sums
%product of natural numbers with successives sums:

% |0 se y=0
% mul(x,y)|
% |x+mul(x,y-1) se y>0

mul(_,0,0):-!.
mul(X,Y,Z):-X>0,Y>0,
Y1 is Y-1,
mul(X,Y1,Z1),Z is X+Z1.

%Calculate the power of one number
%ie power(2,10,R)
power(_,0,1):-!.
power(N,K,R):-K1 is K-1,
power(N,K1,R1),
mul(R1,N,R).


%generate one list of N numbers.
%genList(10,L).
generateList(0,[]).
generateList(N,[X|Xs]):- N > 0,
X is N+1,
N1 is N-1,generateList(N1,Xs).


%formula of perfect numbers (2^p-1)*2^(p-1)
%ie calc(2,10,R)
calc(2,K,R):power(2,K,X),R1 is X-1,primo(R1),
power(2,K-1,R2),
mul(R1,R2,R).

primo(X):-Y is 2, X >1, \+hasFactor(X,Y).

%output the list
noLst([X|_],X).
noLst([_|T],Z):-noLst(T,Z).

%calculate perfect numbers
%ie perfect(12,N).
perfect(N,R):-generateList(N,Xs),noLst(Xs,K),calc(2,K,R).

 
As you have already been told in another forum, if you have predicate sqrt, hasFactor can be written
Code:
hasFactor(N,L):-
	N mod L=:=0.

hasFactor(N,L):-
	L<sqrt(N),
	L2 is L+1,
	hasFactor(N,L2).
 
Status
Not open for further replies.

Part and Inventory Search

Sponsor

Back
Top