Recursive Collatz Conjecture

Question

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 code-golf, the answer with the shortest amount of bytes wins.

Answer 1

Jelly, 24 bytes

×3‘$HḂ?’пL’
Ç1¹?ȷ2Сi1’

Try it online!

Answer 2

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!

Answer 3

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.)

Answer 4

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!

Answer 5

J, ₄₉ 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).

Answer 6

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

Answer 7

APL (Dyalog Unicode), 39 60 53 52 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}⍵}

Answer 8

Perl 6, 56 bytes

{($_,{($_,{$_%2??$_*3+1!!$_/2}...1)-1}...1).head(102)-1}

Try it online!

Returns 101 for a non-terminating sequence.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

Python 2, 99 98 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!

Answer 13

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.

Answer 14

(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)

Answer 15

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

Answer 16

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!