Find all natural divisors of a number (with Prolog)

Question

I want to create a predicate divisors(X,[Y]) which is true if X>1 and Y is the list of all divisors of X starting with X and going down to 1.

What my code right now looks like:

divisors(1,[1]).
divisors(X,[Y,Z|Ys]) :- 
    X>0,
    Y is X,
    Y>Z, 
    divides(X,[Z|Ys]).

divides(X,[Y,Z|Ys]) :-
    Y>Z, 
    0 is X mod Y, 
    divides(X,[Z|Ys]).
divides(X,[1]).

But there are several problems with it:

1. prolog returns an error if asked for the list (e.g. ?-divisors(10,X).)

2. ?- divisors(X,[Y]). Where [Y] is an incomplete list of divisors is true...

---

Edit by Guy Coder

This answer is by the OP and was posted in a comment below.

Moving here so others can see it.

divisors(X,R) :- 
  X > 1, 
  divisors(X,1,[],R). 

divisors(X,D,R,R):-
  D>X.

divisors(N,D0,R0,R) :-
  divisors_0(N,D0,R0,R1), 
  D is D0 + 1, 
  divisors(N,D,R1,R). 

divisors_0(N,D,R0,[D|R0]) :-
  divides(N,D). 

divisors_0(N,D,R0,R0).

divides(N,D) :-
  0 is N mod D.

Op also noted some errors in this version:

1. It doesn't terminate if I ask a wrong statement like (10,[1,2,3]).

2. It throws an error if I ask a statement like (X, [10,5,2,1]). (-> Arguments are not sufficiently initialized.)

Answer 1

While the answer by William is nice and probably faster here is answer closer to what you were writing.

divides(N,D) :-
    0 is N mod D.

divisors_0(N,D,R0,[D|R0]) :-
    divides(N,D).

divisors_0(N,D,R0,R0) :-
    \+ divides(N,D).

divisors(_,0,R,R).

divisors(N,D0,R0,R) :-
    divisors_0(N,D0,R0,R1),
    D is D0 - 1,
    divisors(N,D,R1,R).

divisors(X,R) :-
    X > 1,
    divisors(X,X,[],R), !.

Example:

?- between(1,15,N), divisors(N,Rs).
N = 2,
Rs = [1, 2] ;
N = 3,
Rs = [1, 3] ;
N = 4,
Rs = [1, 2, 4] ;
N = 5,
Rs = [1, 5] ;
N = 6,
Rs = [1, 2, 3, 6] ;
N = 7,
Rs = [1, 7] ;
N = 8,
Rs = [1, 2, 4, 8] ;
N = 9,
Rs = [1, 3, 9] ;
N = 10,
Rs = [1, 2, 5, 10] ;
N = 11,
Rs = [1, 11] ;
N = 12,
Rs = [1, 2, 3, 4, 6, 12] ;
N = 13,
Rs = [1, 13] ;
N = 14,
Rs = [1, 2, 7, 14] ;
N = 15,
Rs = [1, 3, 5, 15].

---

Edit

OP modified their code, see update in question and had some errors.

This version resolves those errors.

divisors(X,R) :-
  (
    var(X)
  ->
    false
  ;
    (
      var(R)
    ->
      X > 1,
      divisors(X,1,[],R)
    ;
      divisors_2(X,R), !
    )
  ).

divisors_2(_,[]).

divisors_2(X,[H|T]) :-
  divides(X,H),
  divisors_2(X,T).

divisors(X,D,R,R):-
  D>X.

divisors(N,D0,R0,R) :-
  divisors_0(N,D0,R0,R1),
  D is D0 + 1,
  divisors(N,D,R1,R).

divisors_0(N,D,R0,[D|R0]) :-
  divides(N,D).

divisors_0(_,_,R0,R0).

divides(N,D) :-
  0 is N mod D.

The first error: It doesn't terminate if I ask a wrong statement like divisors(10,[1,2,3]).

is fixed by adding to divisors/2

(
  var(R)
->
  X > 1,
  divisors(X,1,[],R)
;
  divisors_2(X,R), !
)

and

divisors_2(_,[]).

divisors_2(X,[H|T]) :-
  divides(X,H),
  divisors_2(X,T).

which just processes the list of denominators instead of generating a list.

The second error: It throws an error if I ask a statement like divisors(X, [10,5,2,1]). (-> Arguments are not sufficiently initialized.)

is resolved by further adding to divisor/2

divisors(X,R) :-
  (
    var(X)
  ->
    false
  ;
    (
      var(R)
    ->
      X > 1,
      divisors(X,1,[],R)
    ;
      divisors_2(X,R), !
    )
  ).

which checks if the first parameter X is a variable and if so just returns false. The other option would be to generate an infinite list of answers. While possible it wasn't requested.

Answer 2

In Prolog, it is quite common to use backtracking and propose multiple solutions to the same query. Instead of constructing a list of dividers, we thus can construct a predicate that unifies the second parameter with all divisors. For example:

divisor(N, D) :-
    between(1, N, D),
    0 is N mod D.

This then yields:

?- divisor(12, N).
N = 1 ;
N = 2 ;
N = 3 ;
N = 4 ;
N = 6 ;
N = 12.

The above algorithm is an O(n) algorithm: we scan for divisors linear with the value of the item for which we want to obtain the divisors. We can easily improve this to O(√n) by scanning up to √n, and each time yield both the divisor (of course in case it is a divisor), and the co-divisor, like:

emitco(D, _, D).
emitco(D, C, C) :-
    dif(D, C).

divisor(N, R) :-
    UB is floor(sqrt(N)),
    between(1, UB, D),
    0 is N mod D,
    C is N / D,
    emitco(D, C, R).

This still yield the correct answers, but the order is like a convergent alternating sequence:

?- divisor(12, N).
N = 1 ;
N = 12 ;
N = 2 ;
N = 6 ;
N = 3 ;
N = 4.

?- divisor(16, N).
N = 1 ;
N = 16 ;
N = 2 ;
N = 8 ;
N = 4 ;
false.

We can obtain a list of the divisors by using a findall/3 [swi-doc] or setof/3 [swi-doc]. The setof/3 will even sort the divisors, so we can implement divisors/2 in terms of divisor/2:

divisors(N, Ds) :-
    setof(D, divisor(N, D), Ds).

For example:

?- divisors(2, N).
N = [1, 2].

?- divisors(3, N).
N = [1, 3].

?- divisors(5, N).
N = [1, 5].

?- divisors(12, N).
N = [1, 2, 3, 4, 6, 12].

?- divisors(15, N).
N = [1, 3, 5, 15].

We can use reverse/2 to reverse that result.