# Recursive Collatz Conjecture

The Collatz conjecture postulates that if you take any positive integer, then repeat the following algorithm enough times:

if number is odd, then multiply by three and add one
if number is even, then divide by two


you'll eventually end up at 1. It seems to always work, but it's never been proven that it always does.

You've already golfed calculating how long it takes to get to 1, so I thought I'd switch things up a bit.

Starting with a given positive integer, calculate how long it takes to get to 1 (its "stopping time"). Then find that number's stopping time.

Repeat until you get to 1, or until you get to the entirely arbitrary limit of 100 iterations. In the former case, print how many iterations it took. In the latter case, print "Fail" or some other consistent output of your choice, as long as it's not an integer 1≤n≤100. You may not output an empty string for this option. Outputting an integer outside of the range [1, 100], however, is allowed.

## Examples:

Input: 2
2->1
Output: 1

Input: 5
5->5->5->5->5->...
Output: Fail

Input: 10
10->6->8->3->7->16->4->2->1
Output: 8

Input: 100
100->25->23->15->17->12->9->19->20->7->16->4->2->1
Output: 13

Input: 10^100
10^100->684->126->108->113->12->9->19->20->7->16->4->2->1
Output: 13

Input: 12345678901234567890
12345678901234567890->286->104->12->9->19->20->7->16->4->2->1
Output: 11

Input: 1
--Depending on your code, one of two things may happen. Both are valid for the purposes of this question.
1
Output: 0
--Or:
1->3->7->16->4->2->1
Output: 6


As I calculated 10^100 and 12345678901234567890 using a language that only supports reals for that size, if your language is more accurate you may get different results for those.

## Scoring

As this is , the answer with the shortest amount of bytes wins.

• – cole Jan 8 '18 at 1:29

# Jelly, 24 bytes

×3‘$HḂ?’Ð¿L’ Ç1¹?ȷ2Ð¡i1’  Try it online! • 23 bytes (using ³ instead of ȷ2 is allowed). – Mr. Xcoder Jan 8 '18 at 7:57 # Python 2, 70 bytes f=lambda n,k=0,j=0:n-1and-~f(k*[n/2,n*3+1][n%2]or f(j/99or n,1),k,j+1)  Returns 199 for one hundred or more iterations. Try it online! # Attache, 40 bytes -&3@#@PeriodicSteps[CollatzSize@Max&1]  Try it online! This is a new language that I made. I wanted to get around to making a proper infix language, and this is the result: a mathematica knock-off. Hooray? ## Explanation This is a composition of a few functions. These functions are: • PeriodicSteps[CollatzSize@Max&1] This yields a function which applies its argument until the results contain a duplicate element. This function, CollatzSize@Max&1, is applying CollatzSize to the greater of the input and 1, to avoid the invalid input 0 to CollatSize. • # is a quoted operator; when applied monadically in this sense, it obtains the size of its argument • -&3 is a bonded function, which bonds the argument 3 to the function -, which reads as "minus 3". This is because the PeriodicSteps application yields 0s, which need to be accounted for. (It also neatly handles out-of-bounds numbers like 5, which map to -1.) • Is using your own language really allowed? Cant you just create a langage for each codegolf with only uses some bytes? – Tweakimp Jan 8 '18 at 14:58 • @Tweakimp Of course creating (and using) your own language is allowed. But modifying it so that a task is a single command (after the challenge is posted) is a standard loophole. – caird coinheringaahing Jan 8 '18 at 16:36 • @Tweakimp if it makes you feel any better, I had designed this function before I saw this challenge. I am a language designer, so that's what I do. – Conor O'Brien Jan 8 '18 at 18:45 • It was more a general question wether selfmade languages are allowed, not a negative statement that you used your own. – Tweakimp Jan 13 '18 at 19:20 # J, 49 45 bytes -4 bytes thanks to shorter Collatz Sequence code taken from @randomra's comment here. (2-~[:#(>&1*-:+2&|*+:+>:@-:)^:a:)^:(<101)i.1:  Outputs 101 for invalid results. Try it online! # Explanation Unsurprisingly, this explanation has become quickly outdated. I'm going to leave it in terms of the old 49 byte answer I had, which I'm including below. If you want an update, just let me know. The way that it finds the length of the recursive sequence remains the same, I've just used a shorter Collatz Sequence method. (1-~[:#%&2(1+3&*)@.(2&|)^:(1&<)^:a:)^:(<101)i.1:  ### Finding the length of the Collatz Sequence This section of the code is the following (1-~[:#%&2(1+3&*)@.(2&|)^:(1&<)^:a:)  Here's the explanation: (1 -~ [: # %&2(1+3&*)@.(2&|) ^: (1&<) ^: a:) Given an input n ^: a: Apply until convergence, collecting each result in an array. ^: (1&<) If n > 1 do the following, else return n. (2&|) Take n mod 2. %&2 If n mod 2 == 0, divide by 2. (1+3&*) If n mod 2 == 1, multiply by 3 and add 1. # Get the length of the resulting array. 1 -~ Subtract 1.  Unfortunately, the apply verb (^:) when told to store results stores the initial value too, so it means we're (like always) off by one. Hence why we subtract 1. ### Finding the length of the recursive sequence (1-~[:#%&2(1+3&*)@.(2&|)^:(1&<)^:a:) ^: (< 101) i. 1: Given an input n. ^: (< 101) Apply 100 times, collecting results in an array. (1-~[:#%&2(1+3&*)@.(2&|)^:(1&<)^:a:) Collatz sequence length. i. 1: Index of first 1 (returns 101, the length of the array if 1 not found).  • If you don't mind using the header section, this will perhaps more accurately showcase your answer – Conor O'Brien Jan 8 '18 at 1:44 • @ConorO'Brien I don't at all -- I didn't really know how to get it formatted as such (but I'll be stealing yours from now on). Thanks – cole Jan 8 '18 at 2:01 • ​A​n​y​t​i​m​e​! – Conor O'Brien Jan 8 '18 at 2:06 • 38 bytes with *i.~(<101)1&(#@}.a:2&(<*|{%~,*+1+])])] should be equivalent – miles Jan 9 '18 at 1:34 # C (gcc), 75 bytes i,j;f(n){for(j=0;(i=n)&&j++<100;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j-1;}  Returns -1 for n>=100 iterations. Try it online! # C (gcc), 73 bytes i,j;f(n){for(j=-1;(i=n)&&j++<99;)for(n=0;i-1;++n)i=i&1?i*3+1:i/2;i=!i*j;}  Returns 0 for n>=100 iterations. Try it online! # JavaScript (ES6), 57 bytes Returns true when it fails. Returns 0 for 1. f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i  ### Test cases f=(n,k=i=0)=>n>1?f(n&1?n*3+1:n/2,k+1):k?i>99||f(k,!++i):i console.log(f(2)) // 1 console.log(f(5)) // fail console.log(f(10)) // 8 console.log(f(100)) // 13 console.log(f(1)) // 0 • I am sceptical if your program happens to calculate the correct result apart from overflow / inaccuracy or if rather the OP derived their results using a language with similar number implementations (I assume they did not calculate all test cases by hand). – Jonathan Frech Jan 8 '18 at 1:32 • @JonathanFrech Indeed. It turns out both results were equally invalid. – Arnauld Jan 8 '18 at 6:50 # APL (Dyalog Unicode), 39605352 49 bytes -3 bytes thanks to @ngn 0∘{99<⍺:⋄1=⍵:0⋄1+(⍺+1)∇{1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵}⍵}  Try it online! Uses @ngn code for Collatz, but previously used @Uriel's code. Here's the old version that didn't meet the specification: {1=⍵:0⋄1+∇{1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}⍵}  • 2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2 -> 1+∇⊃⍵⌽0 1+.5 3×⍵ – ngn Jan 16 '18 at 5:29 # Perl 6, 56 bytes {($_,{($_,{$_%2??$_*3+1!!$_/2}...1)-1}...1).head(102)-1}


Try it online!

Returns 101 for a non-terminating sequence.

# Husk, 21 bytes

←€1↑101¡ȯ←€1¡?½o→*3¦2


Try it online! Returns -1 on failure, 0 on input 1.

## Explanation

←€1↑101¡ȯ←€1¡?½o→*3¦2  Implicit input (a number).
?½o→*3¦2  Collatz function:
?     ¦2   if divisible by 2,
½         then halve,
o→*3     else multiply by 3 and increment.
ȯ←€1¡?½o→*3¦2  Count Collatz steps:
¡           iterate Collatz function and collect results in infinite list,
€1            get 1-based index of 1,
ȯ←              decrement.
¡               Iterate this function on input,
↑101                take first 101 values (initial value and 100 iterations),
←€1                    get index of 1 and decrement.


# C (gcc), 70 73 bytes

g(x){x=x-1?g(x%2?3*x+1:x/2)+1:0;}f(x,m){for(m=0;(x=g(x))&&100>m++;);x=m;}


Try it online!

Returns 101 when number of iterations exceeds 100.

• Welcome to PPCG! This answer isn't quite valid, because all function submissions need to be reusable. I think you can fix this by inserting m=0 into your f (probably even making use of the currently empty for intiailiser to save one a ;). – Martin Ender Jan 9 '18 at 12:37

# Clean, 146 ... 86 bytes

-11 bytes thanks to Ørjan Johansen

import StdEnv
?f l n=hd[u\\1<-iterate f n&u<-l]

?(?(\b|isOdd b=3*b+1=b/2)[0..])[0..99]


As a partial function literal.

Try it online!

Aborts with hd of [] if the number of iterations exceeds 100.
Exits with Heap Full for inputs above ~2^23 unless you specify a larger heap size.

• I'm starting to understand some Clean syntax (as it differs from Haskell) from your answers... you can shorten that with a helper function j f l n=hd[u\\1<-iterate f n&u<-l]. – Ørjan Johansen Jan 10 '18 at 0:42
• @ØrjanJohansen Thanks! – Οurous Jan 10 '18 at 0:56
• You don't need the \a=...a part, it curries. (Or eta reduces.) – Ørjan Johansen Jan 10 '18 at 1:16
• @ØrjanJohansen oh, missed that, thanks! – Οurous Jan 10 '18 at 1:41

# Python 2, 9998 97 bytes

• Saved a byte by using c and t or f instead of t if c else f.
• Saved a byte by outputting -1 instead of f or 'f' for non-halting inputs.
exec"f,F="+"lambda n,i=0:n<2and i or %s"*2%("f([n/2,3*n+1][n%2],-~i),","i>99and-1or F(f(n),-~i)")


Try it online!

## BiwaScheme, 151 chars

(define(f n i s)(if(= s 0) 'F(if(= n 0)i(f(letrec((c(lambda(m k)(if(= m 1)k(c(if(=(mod m 2)0)(/ m 2)(+(* m 3)1))(+ k 1))))))(c n 0))(+ i 1)(- s 1)))))


You can try it here.

# R, 119 107 bytes

Partially uses Jarko Dubbeldam's collatz code from here. Returns 0 for >100 iterations (failure).

pryr::f(x,{N=n=0
while(x-1){while(x-1){x=if(x%%2,3*x+1,x/2);n=n+1}
x=n
n=0
N=N+1
if(N==100)return(0)}
N})


Try it online!

# APL NARS, 115 bytes, 63 chars

{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}


Probably using loops it would be more clear... There are 4 functions, 2 nested and ricorsive, and the first only for define and initialize to =0, the variable d, seen from the 2th function as a global variable counter.

q←{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}


This 3th function, would be the function that return how many call there are for resolve the Collatz conjecture for its arg

{⍵=1:d⋄99<d+←1:¯1⋄∇q⍵}


This is the 2th function, if has its arg =1,stop its recursion and return d the number of time it is called itself-1; else if itself is called more than 99times stop its recursion and return -1(fail) else calculate Collatz conjecture for its arg, and call itself for the Collatz sequence length value. For me even if all this seems run could be a big problem if is defined a global variable and one variable in a function of the same name, when the programmer sees it as just a local variable.

  f←{d←0⋄{⍵=1:d⋄99<d+←1:¯1⋄∇{c←0⋄{1=⍵:c⋄c+←1⋄2∣⍵:∇1+3×⍵⋄∇⍵÷2}⍵}⍵}⍵}
f 2
1
f 3
5
f 5
¯1
f 10
8
f 100
13
f 12313
7
f 1
0


(Emacs, Common, ...) Lisp, 105 bytes

Returns t for iterations > 100

(defun f(n k c)(or(> c 100)(if(= n 1)(if(= k 0)c(f k 0(1+ c)))(f(if(oddp
n)(+ n n n 1)(/ n 2))(1+ k)c))))


Expanded:

(defun f (n k c)
(or (> c 100)
(if (= n 1)
(if (= k 0) c
(f k 0 (1+ c)))
(f (if (oddp n) (+ n n n 1) (/ n 2))
(1+ k) c))))
(f (read) 0 0)