PROLOG : Given a number X, find all multiples of 4 less or equal than X

user_7623196 0
Viewed 56

I have the following program:

list4(N, L) :-
  list4(0, N, L).

list4(N, N, [N]).
list4(N0, N, [N0| List]) :-
  N0 < N,
  N1 is N0+1,
  list4(N1, N, List).

When i change the line N1 is N0+1 to N1 is 4*N0 i get stack limit exceeded error.

My expected result is

list4(10,L).
L = [4,8]
prolog
2 Answers

Two problems with the 4*N0 version:

  1. In list4/2 you initialize list4/3 with N0=0, which, multiplied with anything, always stays 0. That causes the infinite recursion. As you want multiples of four, you can just keep increasing N0 by one in each step and multiply it by 4 before putting it into the list.

  2. The anchor relies on your count variable arriving at N exactly, but N0 * 4 overshoots. The first rule of list4/3 has to cover the rest of the cases with N0*4 > N as well. To also include the upper limit in the result, we can make the anchor stop at values larger than the limit and handle the upper bound itself in the second rule.

Expressed in code:

list4(N, L) :-
  list4(1, N, L).

list4(N0, N, []) :- N4Times is N0*4,N4Times > N.
list4(N0, N, [N4Times| List]) :-  
  N4Times is N0*4,
  N4Times =< N,
  N1 is N0 + 1,
  list4(N1, N, List).

Results in:

?- list4(10,L).
L = [4, 8] ;
false.
?- list4(8,L).
L = [4, 8] ;
false.
user_146275870

You can initialize the accumulator with 0 and increment it by 4 at each step.

% list4(+Upperbound, -MultiplesOfFour)

list4(U, M) :- 
    list4(0, U, M).

list4(A, U, L) :-
    M is A+4,
    (   M =< U
    ->  L = [M|Ms],
        list4(M, U, Ms)
    ;   L = [] ).

Examples:

?- list4(10, L).
L = [4, 8].

?- list4(8, L).
L = [4, 8].

?- list4(20, L).
L = [4, 8, 12, 16, 20].

?- list4(30, L).
L = [4, 8, 12, 16, 20, 24, 28].

?- list4(3, L).
L = [].
user_115359400
Related