Yet another perfect number program 
Author Message
 Yet another perfect number program

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



Fri, 19 Jun 1992 09:48:00 GMT  
 Yet another perfect number program
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!



Fri, 19 Jun 1992 18:17:00 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. Yet another perfect number program

2. New user need help with perfect numbers.

3. Perfect Numbers

4. Perfect Numbers

5. ASM to test Perfect Number

6. Finding perfect numbers

7. Perfect Number

8. Perfect Numbers, Complexity

9. perfect numbers

10. Perfect Programming Language

11. Perfect Programming Language

12. Perfect Programming Language

 

 
Powered by phpBB® Forum Software