Prolog - get the factors for a given number doesn't stop?

Question

I need to find the factors of a given number , e.g :

?- divisors2(40,R).
R = [40,20,10,8,5,4,2,1].

The code :

% get all the numbers between 1-X 
range(I,I,[I]).
range(I,K,[I|L]) :- I < K, I1 is I + 1, range(I1,K,L).
% calc the modulo of each element with the given number :
% any x%y=0 would be considered as part of the answer 
divisors1([],[],_).
divisors1([H|T],S,X):-divisors1(T,W,X),Z is X mod H,Z==0,S=[H|W].
divisors1([_|T],S,X):-divisors1(T,S,X).
divisors2(X,Result) :-range(1,X,Result1),divisors1(Result1,Result,X).

But when I run divisors2(40,RR). I get infinite loop and nothing is presented to the screen.

Why ?

Regards

Answer 1

You have a bug here

divisors1([H|T],S,X):-
   divisors1(T,W,X),
   Z is X mod H,
   Z==0,S=[H|W]. <=== here

If Z is Zero then S = [H|W] else S = W.

Answer 2

If you correct your range (use a cut for the end-of-recursion clause), you will get it sort of working. You do not immediately succeed upon finding all divisors though.

A solution using your general idea, but also built-ins between/3 and bagof/3 (to make typing a bit easier):

divisors(X, Divs) :- bagof(D, divs(X,D), Divs).
divs(X,D) :- between(1,X,D), 0 is X mod D.

Please note that this solution returns the divisors in increasing order.

Answer 3

You are asking why you get an infinite loop for the query divisors2(40,R). I almost wanted to explain this to you using a failure-slice. Alas ...

... the answer is: No, you don't get an infinite loop! And your program also finds an answer. It's

   R = [1,2,4,5,8,10,20,40]

which looks reasonable to me. They are in ascending order, and you wanted a descending list, but apart from that, that is a perfect answer. No kidding. However, I suspect that you were not patient enough to get the answer. For 36 I needed:

?- time(divisors2(36,R)).
   % 10,744,901,605 inferences, 2248.800 CPU in 2252.918 seconds (100% CPU, 4778061 Lips)
   R = [1,2,3,4,6,9,12,18,36]
;  ... .

Quite unusual ... for a list with at most 36 meager integers Prolog needed 10 744 901 605 inferences, that is less than 2³⁴. Does this ring a bell? In any case, there are problems with your program. In fact, there are two quite independent problems. How can we find them?

Maybe we are looking at the wrong side. Just go back to the query. Our first error was how we used Prolog's toplevel. We were very impressed to get an answer. But Prolog offered us further answers! In fact:

?- time(divisors2(36,R)).
   % 10,744,901,605 inferences, 2248.800 CPU in 2252.918 seconds (100% CPU, 4778061 Lips)
   R = [1,2,3,4,6,9,12,18,36]
;  % 10 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 455892 Lips)  R = [1,2,3,4,6,9,12,18]
;  % 917,508 inferences, 0.192 CPU in 0.192 seconds (100% CPU, 4789425 Lips)
   R = [1,2,3,4,6,9,12,36]
; ... .

This gets too tedious. Maybe a tiny example suffices?

?- divisors2(6,R).
   R = [1,2,3,6]
;  R = [1,2,3]
;  R = [1,2,6]
;  R = [1,2]
;  R = [1,3,6]
;  R = [1,3]
;  R = [1,6]
;  R = [1]
;  R = [2,3,6]
;  R = [2,3]
;  R = [2,6]
;  R = [2]
;  R = [3,6]
;  R = [3]
;  R = [6]
;  R = []
;  false.

More than enough! Maybe we stick to the minimal example [] and restate it:

?- divisors2(6,[]).
   true
;  false.

Clearly, that's not what we expected. We wanted this to fail. How to localize the problem? There is one general debugging strategy in Prolog:

If a goal is too general, specialize the program.

We can specialize the program by adding further goals such that above query still succeeds. I will add false and some (=)/2 goals. false is particularly interesting because it wipes out an entire clause:

?- divisors2(6,[]).

range(I,I,[I]) :- I = 6.
range(I,K,[I|L]) :- K = 6,
   I < K,
   I1 is I + 1,
   range(I1,K,L).

divisors1([],[],X) :- K=6.
divisors1([H|T],S,X):- false,
   divisors1(T,W,X),
   Z is X mod H,
   Z=0,
   S=[H|W].
divisors1([_|T],S,X):- S = [], X = 6,
   divisors1(T,S,X).

divisors2(X,Result) :- X = 6, Result = [].
   range(1,X,Result1),
   divisors1(Result1,Result,X).

Somewhere in the remaining part something is too general! In fact the recursive rule of divisors1/3 is too general. This new modified program of yours is called a slice that is a specialization of our original program.

Several ways to fix this, the most naive way is to add the corresponding condition like so:

divisors1([],[],_).
divisors1([H|T],S,X):-
   divisors1(T,W,X),
   0 =:= X mod H,
   S=[H|W].
divisors1([H|T],S,X):-
   divisors1(T,S,X),
   0 =\= X mod H.

However, the performance of the program did not improve. To see this, I will again specialize this program:

divisors1([],[],_) :- false.
divisors1([H|T],S,X):-
   divisors1(T,W,X), false,
   0 =:= X mod H,
   S=[H|W].
divisors1([H|T],S,X):-
   divisors1(T,S,X), false,
   0 =\= X mod H.

Thus: No matter what is there behind the false, this program will try at least 3 * 2^N inferences for a list of length N.

By putting the recursive goals last we can avoid this.