# How do I modify my code to detect cycles in this Collatz-like recursion?

A popular variant of the Collatz recursion is the following. Given a positive integer $$n_i$$,

• If $$n_i$$ is even, $$n_{i+1}=n/2$$,
• If $$n_i$$ is odd, $$n_{n+1}=3n-1$$.

The Mathematica code I'm using to display the list of $$n_i$$ for a given starting number is:

collatz[x_] :=  NestWhileList[If[Mod[#, 2] == 0, #/2, #*3 - 1] &, x, # != 1 &]


However, this variant of the Collatz has cycles other than the trivial $$\{4,2,1\}$$, for instance for the starting values $$5$$ and $$17$$. The above code only stops once $$1$$ is reached, which obviously creates an infinite loop for these inputs.

How do I modify the above code so that other "loops" are also taken into account? I tried modifying the stopping condition to include something like # != x but that condition is obviously fulfilled at the start of the loop, and introducing variables that check whether it is the "first" iteration make the code very messy.

Are there any "nice" ways to do this?

Use more parameters for NestWhileList as follows, where the final adjustable parameter max is arbitrarily set to 100. Increase max as required.

c1[x_] := NestWhileList[If[EvenQ[#], #/2, 3 # - 1] &, x, # != 1 &, 1, 100]


Alternatively, try

c2[x_] := NestList[If[EvenQ[#], #/2, 3 # - 1] &, x, 100]


Then use FindTransientRepeat to look for cycles.

FindTransientRepeat[c1, 2]


{{}, {17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34}}

FindTransientRepeat[c2, 2]


{{26, 13, 38, 19, 56, 28}, {14, 7, 20, 10, 5}}

Try this:

iter[x_Integer] := If[EvenQ[x], x/2, 3 x - 1]
collatz[x_Integer] := Prepend[NestWhileList[iter, iter[x], (# != 1 && # != x) &], x]

collatz
(* {6, 3, 8, 4, 2, 1} *)
collatz
(* {5, 14, 7, 20, 10, 5} *)

• Some values do not work with this method, for instance $9$: it enters a cycle but is not part of a cycle itself. – Klangen Aug 25 '19 at 18:03
• @Klangen Well, to be fair, that was not part of your question :-) Here I show you how to implement the # != x condition skipping the first step. Whether that is enough to prevent all cycles I don't know. – AccidentalFourierTransform Aug 25 '19 at 18:09
• Fair enough! Thank you for your code anyway – Klangen Aug 25 '19 at 18:15