collatz-list implementation using Prolog

Question

I am trying to create a function called collatz_list in Prolog. This function takes two arguments, the first one is a number and the second in a list. This list will be my output of this function. So, here's my function:

collatz_list(1,[1]).
collatz_list(N,[H|T]) :-
   N > 1,
   N mod 2 =:= 0,
   collatz_list(N, [H|T]).  
collatz_list(N,[H|T]) :-
   N > 1,
   N mod 2 =:= 1,
   N is N*3 +1,
   collatz_list(N,[H|T]).

I am struggling with creating the output list. Can anyone help me on that?

Thanks.

Haile · Accepted Answer · 2012-12-08T15:39:38.890

3

Assuming you want to write a collatz_list/2 predicate with parameters (int, list), where list is the collatz sequence starting with int and eventually ending with 1 (we hope so! It's an open problem so far); you just have to code the recursive definition in the declarative way.

Here's my attempt:

/* if N = 1, we just stop */
collatz_list(1, []).

/* case 1: N even
   we place N / 2 in the head of the list
   the tail is the collatz sequence starting from N / 2 */
collatz_list(N, [H|T]) :-
    0 is N mod 2,
    H is N / 2, 
    collatz_list(H, T), !. 

/* case 2: N is odd
   we place 3N + 1 in the head of the list
   the tail is the collatz sequence starting from 3N + 1 */
collatz_list(N, [H|T]) :-
    H is 3 * N + 1, 
    collatz_list(H, T).

Modified version, includes starting number

Let's test it:

full_list(N, [N|T]) :-
    collatz_list(N, T).

collatz_list(1, []).

collatz_list(N, [H|T]) :-
    0 is N mod 2,
    H is N / 2, 
    collatz_list(H, T), !. 

collatz_list(N, [H|T]) :-
    H is 3 * N + 1, 
    collatz_list(H, T). 

?- full_list(27, L).
L = [27, 82, 41, 124, 62, 31, 94, 47, 142|...].

edited Dec 08 '12 at 15:39

answered Dec 08 '12 at 13:10

Haile

3,120
3
24
40

Are you sure that divide is / and not //. I ran your code and I am getting this error: collatz_list/2: Undefined procedure: (-)/2 – Stranger Dec 08 '12 at 15:11
Ok, worked but now if you look at your answer for collatz-list(27), it doesnt display the 27 itself. I think it should include 27. – Stranger Dec 08 '12 at 15:21
Well, modify it to include the starting number. – Haile Dec 08 '12 at 15:23
Dude, that's what I was trying to do to begin with. I don't know the syntax of it. I want to append the N and then recursively call the function. So, I am doing like this: [N | collatz-list(H, T)]. But this doesnt seem to be working. – Stranger Dec 08 '12 at 15:28
Any ideas on how to append the head to the tail of the list? – Stranger Dec 08 '12 at 15:40
Added an additional full_list/2 predicate to include the first number. – Haile Dec 08 '12 at 15:40
Is there a way of not using full_list and creating a list in the function? – Stranger Dec 08 '12 at 15:48

score 3 · Answer 2 · edited May 23 '17 at 12:15

First, we define the simple auxiliary predicate collatz_next/2 to performs a single Collatz step:

collatz_next(X,Y) :-
   X >= 1,
   (  X =:= 1       -> Y = 1
   ;  X mod 2 =:= 0 -> Y is X // 2
   ;                   Y is 3*X + 1
   ).

To advance to a fixed point, we use the meta-predicates fixedpoint/3 and fixedpointlist/3:

?- fixedpoint(collatz_next,11,X).
X = 1.                                            % succeeds deterministically

?- fixedpointlist(collatz_next,11,Xs).
Xs = [11,34,17,52,26,13,40,20,10,5,16,8,4,2,1].   % succeeds deterministically

Both meta-predicates used in above query are based on the monotone control construct if_/3 and the reified term equality predicate (=)/3, and can be defined as follows:

:- meta_predicate fixedpoint(2,?,?).
fixedpoint(P_2, X0,X) :-
   call(P_2, X0,X1),
   if_(X0=X1, X=X0, fixedpoint(P_2, X1,X)).

:- meta_predicate fixedpointlist(2,?,?).
fixedpointlist(P_2,X0,[X0|Xs]) :-
   call(P_2, X0,X1),
   if_(X0=X1, Xs=[], fixedpointlist(P_2,X1,Xs)).

collatz-list implementation using Prolog

2 Answers2

Linked