Path: utzoo!attcan!uunet!mcvax!prlb2!kulcs!bimandre
From: bimandre@kulcs.uucp (Andre Marien)
Newsgroups: comp.lang.prolog
Subject: Yet another perfect number program
Message-ID: <1564@kulcs.kulcs.uucp>
Date: 10 Jan 89 09:48:46 GMT
Reply-To: bimandre@kulcs.UUCP ()
Organization: B.I.M., Everberg, Belgium
Lines: 60

The following program is about 4 times faster than all previous posted
versions, using the normal search method.
It would run a lot faster if you new perfect numbers are all even.
I could not prove that in short time. Anyone ?
Timings were done with BIM_Prolog.

perfect(_X) :-
	gen(_X,1),
	sumd(_X,1,2) .

sumd(_X,_PS,_Y) :-
	_X mod _Y =:= 0, !,
	_NS is _PS + _X/_Y + _Y,
	check(_X,_NS,_Y) .
sumd(_X,_PS,_Y) :-
	_NY is _Y + 1,
	_NY*_NY =< _X,
	sumd(_X,_PS,_NY) .

check(_X,_S,_Y) :-
	_S < _X, !,
	_NY is _Y + 1,
	_NY*_NY =< _X,
	sumd(_X,_S,_NY) .
check(_X,_S,_Y) :-
	_S > _X, !,
	_Y*_Y =:= _X,
	_X =:= _S - _Y .
check(_X,_S,_Y) :-
	_Y*_Y < _X,
	_NY is _Y + 1,
	nodiv(_X,_NY) .

nodiv(_X,_Y) :-
	_Y*_Y =< _X, !,
	_X mod _Y =\= 0,
	_NY is _Y + 1,
	nodiv(_X,_NY) .
nodiv(_X,_Y) .

gen(_N,_N) .
gen(_N,_S) :-
	_NS is _S + 1,
	gen(_N,_NS) .

z :- perfect(_N), write(_N) .

test :- perfect(_N), _N >= 8128, ! .
timetest :- time(test) .

timing results (SUN 3/50)

42.66
42.5


Andre' Marien
B.I.M.

mcvax!prlb2!kulcs!bimandre