Factors of a number

Question

So I am relatively new to Prolog, and while this problem is easy in many other languages I am having a lot of trouble with it. I want to generate a List of factors for a number N. I have already built a predicate that tells me if a number is a factor:

% A divides B
% A is a factor of B
divides(A,B) :- A =\= 0, (B mod A) =:= 0.

% special case where 1 // 2 would be 0
factors(1,[1]) :- !.

% general case
factors(N,L):- N > 0, factor_list(1, N, L).
factor_list(S,E,L) :- S =< E // 2, f_list(S,E,L).

f_list(S,E,[])    :- S > E // 2, !.
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T).
f_list(S,E,L)     :- S1 is S+1, f_list(S1,E,L).

Any help would be appreciated.

EDIT

I pretty much changed my entire solution, but for some reason predicates like factors(9, [1]) return true, when I only want factors(9, [1,3]) to return true. Any thoughts?

if you include 1 in factors of 9, why not 9 also? Do you mean just prime factors, or all the divisors of a number? 6 is a divisor of 72, just not a prime one, right? — Will Ness, Mar 31 '13 at 19:57
@WillNess 9 is just implicitly included. For this purpose we are only examining [1, N/2] — Hunter McMillen, Mar 31 '13 at 19:58
@WillNess I kind of want the entire factor list to be the only predicate that returns true. so `factors(72, [6])` should be false, and `factors(72, [1,2,3,4,6,8,9,12,18,24,36])` would be true. Any thoughts? — Hunter McMillen, Mar 31 '13 at 20:01
to do this efficiently is not a trivial task in any language, not that I'm aware of. The usual way is to find prime factorization {p_i,k_i} and generate the factors from it. — Will Ness, Mar 31 '13 at 20:02
@WillNess Well right now it works in the sense that if I do `factors(9, L)` `L` will be `[1,3]`, but `factors(9,[1])` still returns true — Hunter McMillen, Mar 31 '13 at 20:03
See http://stackoverflow.com/questions/14273559/prolog-get-the-factors-for-a-given-number-doesnt-stop/14288853#14288853 — false, Apr 02 '13 at 15:52
@false That wasn't the problem I was trying to solve. My program already ended normally. — Hunter McMillen, Apr 02 '13 at 19:11
@false could you clarify please, does this early unification problem relates to the steadfastness that you always mention? can we say that postponing the unifications makes it steadfast? Or is it "monotonic"? — Will Ness, Apr 03 '13 at 08:16
@WillNess: The original def. is not steadfast because `factors(9, [1])` succeeds, but `factors(9, L), L = [1]` fails. So "output" arguments should be always steadfast. Monotonicity (in the sense of monotonic logic) is not directly related to this. — false, Apr 03 '13 at 08:36

Will Ness · Accepted Answer · 2013-04-03T07:05:14.223

Here's why factors(9,[1]) is true: the timing of attempted instantiations (that is to say, unifications) is off:

f_list(S,E,[])    :- S > E // 2, !.
f_list(S,E,[S|T]) :- divides(S,E), !, S1 is S+1, f_list(S1, E, T).
f_list(S,E,L)     :- S1 is S+1, f_list(S1,E,L).

%%  flist(1,9,[1]) -> (2nd clause) divides(1,9), S1 is 2, f_list(2,9,[]).
%%  flist(2,9,[])  -> (3rd clause) S1 is 3, f_list(3,9,[]).
%% ... 
%%  flist(5,9,[])  -> (1st clause) 5 > 9 // 2, !.

because you pre-specify [1], when it reaches 3 the tail is [] and the match with the 2nd clause is prevented by this, though it would succeed due to divides/2.

The solution is to move the unifications out of clauses' head into the body, and make them only at the appropriate time, not sooner:

f_list(S,E,L) :- S > E // 2, !, L=[].
f_list(S,E,L) :- divides(S,E), !, L=[S|T], S1 is S+1, f_list(S1, E, T).
f_list(S,E,L) :- S1 is S+1, f_list(S1,E,L).

The above usually is written with the if-else construct:

f_list(S,E,L) :- 
  ( S > E // 2   -> L=[]
  ; divides(S,E) -> L=[S|T], S1 is S+1, f_list(S1, E, T)
  ;                          S1 is S+1, f_list(S1, E, L)
  ).

Also you can simplify the main predicate as

%% is not defined for N =< 0
factors(N,L):- 
  (  N =:= 1 -> L=[1]
  ;  N >= 2  -> f_list(1,N,L) 
  ).

score 1 · Answer 2 · answered Sep 07 '13 at 23:10

Personally, I use a somewhat simpler looking solution:

factors(1,[1]):- true, !.
factors(X,[Factor1|T]):- X > 0,
 between(2,X,Factor1), 
 NewX is X // Factor1, (X mod Factor1) =:= 0,
 factors(NewX,T), !.

This one only accepts an ordered list of the factors.

score 1 · Answer 3 · answered Jul 20 '14 at 15:25

Here is a simple enumeration based procedure.

factors(M, [1 | L]):- factors(M, 2, L).
factors(M, X, L):- 
   residue(M, X, M1), 
   ((M==M1, L=L1); (M1 < M, L=[X|L1])),
   ((M1=1, L1=[]); (M1 > X, X1 is X+1, factors(M1, X1, L1))).

residue(M, X, M1):-
  ((M < X, M1=M);
   (M >=X, MX is M mod X, 
     (MX=0, MM is M/X, residue(MM, X, M1);
      MX > 0, M1=M))).

Factors of a number

3 Answers3