Collatz Conjecture (OEIS A006577)

Question

This is the Collatz Conjecture (OEIS A006577):

• Start with an integer n > 1.
• Repeat the following steps:
  • If n is even, divide it by 2.
  • If n is odd, multiply it by 3 and add 1.

It is proven that for all positive integers up to 5 * 2⁶⁰, or about 5764000000000000000, n will eventually become 1.

Your task is to find out how many iterations it takes (of halving or tripling-plus-one) to reach 1.

Relevant xkcd :)

Rules:

• Shortest code wins.
• If a number < 2 is input, or a non-integer, or a non-number, output does not matter.

Test cases

2  -> 1
16 -> 4
5  -> 5
7  -> 16

Answer 1

Emojicode, 139 bytes

🐖🔢➡️🚂🍇🍮a🐕🍮i 0🔁❎😛1a🍇🍊😛1🚮a 2🍇🍮a➕1✖3a🍉🍓🍇🍮a➗a 2🍉🍮i➕1i🍉🍎i🍉

Try it online!

Answer 2

Clean, 82 bytes

import StdEnv
?n=snd(until(\(e,_)=e<2)(\(e,i)=(if(isOdd e)(3*e+1)(e/2),i+1))(n,0))

Try it online!

Answer 3

Stax, 12 bytes^CP437

ÄFl,rBoU¡£&╦

14 bytes when unpacked,

1{h_3*^\_@gt%v

Run and debug online!

Adaptation of https://github.com/tomtheisen/stax/blob/master/testspecs/golf/CollatzTest.staxtest .

Answer 4

SNOBOL4 (CSNOBOL4), 96 bytes

	N =INPUT
T	X =X + 1
	N =GT(REMDR(N,2)) 3 * N + 1	:S(O)
	N =N / 2
O	OUTPUT =EQ(N,1) X	:F(T)
END	

Try it online!

Answer 5

Add++, 50 bytes

D,f,@,dd2/i@3*1+$2%D
+?
-1
W,+1,$f>x,},+1,},-1
}
O

Try it online!

-5 bytes thanks to rubber duck golfing!

How it works

D,f,@,		; Define a function 'f' that takes one argument
		; Example argument:	[10]
	dd	; Triplicate;	STACK = [10 10 10]
	2/i	; Halve;	STACK = [10 10 5]
	@	; Reverse;	STACK = [5 10 10]
	3*1+	; (n*3)+1;	STACK = [5 10 31]
	$	; Swap;		STACK = [5 31 10]
	2%	; Parity;	STACK = [5 31 0]
	D	; Select;	STACK = [5]

+?		; Take input; 	x = 10;	y = 0;
-1		; Decrement;	x = 9;	y = 0;

W,		; While x != 0:
	+1,	;  Increment;	x = 10;	y = 0;
	$f>x,	;  Call 'f';	x = 5;	y = 0;
	},+1,	;  Increment y;	x = 5;	y = 1;
	},-1	;  Decrement x;	x = 4;	y = 1;

}		; Swap to y;	x = 0;	y = 6;
O		; Output y;

Answer 6

dc, 30 28 bytes

?[d5*2+d2%*+2/d1<f1+]dsfx1-p

This uses the formula from Jo King's answer, slightly adapted so we dup after adding 2.

Explanation

?                             # read input
 [            d1<f  ]dsfx     # repeat until we reach 1 
  d5*2+d2%*+2/                # n → (n + (5n+2)%2 * (5n+2)) / 2
                  1+          # count iterations
                         1-p  # decrement and print result

---

Previous answer: 30 bytes

?[6*4+]sm[d2~1=md1!=f]dsfxz1-p

We keep all the intermediate results on the stack, then count the size of the stack. We save bytes by always doing the division by two, but if the remainder is 1, then we multiply by 6 and add 4 (3 for the remainders and 1 for the Collatz constant). The final stack count contains all the numbers we've seen; the number of operations is one less than that.

Explanation

?                               # input

[6*4+]sm                        # helper function

[d2~1=md1!=f]dsfx               # recursion

z1-p                            # print result

Answer 7

Julia 0.6, 43 bytes

c(n,l=0)=n<2?l:n%2>0?c(3n+1,l+1):c(n/2,l+1)

Try it online!

Answer 8

Ahead, 38 bytes

Il&+1t~j+1*3\~/2<~<
>:1)k~tO@~:k\:  nl

Try it online!

Answer 9

Ruby, 77 72 bytes

b=0;a=gets.to_i;loop{if a==1;p b;exit;end;a.odd?? (a*=3;a+=1):a/=2;b+=1}

Definitely not the shortest, but not the most unreadable or hard to follow either. Try it online!

a.odd?? (a*=3;a+=1): uses the ternary operator, which is a short form of if/then/else. It looks like boolean ? instruction : instruction, with the first instruction being if the boolean is true, and the second being if it isn't. Therefore trailing question mark and colon.

*= and /= are the multiplication and division versions of += in Ruby.

Ungolfed version:

counter = 0
input = gets.to_i
loop do
  if input = 1
    print counter
    exit
  end
  if input.odd?
    input *= 3
    input += 1
  else
    input /= 2
  end
  counter += 1
end

Answer 10

SmileBASIC, 54 bytes

INPUT N
WHILE N-1D=1AND N
C=C+1N=N*3*D+D+N/2*!D
WEND?C

Answer 11

Haskell, 47 bytes

c n|n==1=0|even n=1+c(div n 2)|odd n=1+c(3*n-1)

Ungolfed:

c n
    | n == 1 = 0
    | even n = 1 + c (div n 2)
    | odd n  = 1 + c (3*n-1)

A recursive function that returns the number of times it's been run, excluding when n==1.

Answer 12

HBL, 16 15 bytes

?(%.)(+(*.<))(/.2
?(-.)(-+?().

Try it!

Explanation

Helper function:

?(%.)(+(*.<))(/.2
?                  If
   .               the argument
 (% )              is odd:
     (+     )       Increment
       (*  )        the product of
         .          the argument
          <         and 3
                   Else:
             (/     Divide
               .    the argument
                2   by 2

Main function:

?(-.)(-+?().
?             If
 (- )         decrementing
   .          the argument
              is truthy (nonzero):
     (-        Chain these functions together:
       +        Increment
        ?       Call current function recursively
         ()     Call previous function
           .   and apply to the argument

The use of the chain macro may be easier to understand in Thimble, HBL's ungolfed companion language:

(-+?().)
=>
(chain inc recur prev arg1)
=>
(inc (recur (prev arg1)))

Answer 13

Rust, 67 bytes

|mut n|{let mut u=0;while n!=1{if n%2==0{n/=2}else{n=3*n+1}u+=1}u};

Try it online!

Nice way of practicing rust

Answer 14

rusty_deque, 85 bytes

{dup~{3~*~1~+~}~{2~swap~/~}~{dup~2~swap~%~0~=~}~ite~}~{dup~1~<~}~while~pop~len~lb~ll~

Explanation

# start with n on the right of the deque
{                                   # begin while block
 dup~                               # dup to get next step
     {3~*~1~+~}~                    # when n is odd, push 3*n+1
     {2~swap~/~}~                   # when n is even, push n/2
     {dup~2~swap~%~0~=~}~           # conditional, is n even?
     ite~                           # if
}~                                  # end while block
  {dup~1~<~}~ while~                # while n > 1
                    pop~            # delete extra 1
                        len~ lb~    # convert the stack to a list
                                ll~ # pop list, push len of list

Answer 15

Knight, 37 bytes

;=n+0P;=iT;W-1=nI%n 2+1*3n/n 2=i+1iOi

Try it online!

Answer 16

><> (Fish), 31 bytes

:1=?\::2%?\2,
;nl~/i+1*3/
|.!0/

Try it

Answer 17

Punchtape, 405 bytes & Punchcode, 50 bytes

I did this just for fun and showcase

Punchtape is an esoteric language trying to imitate punched tape, a form of data storage widely used by computers in the 1950s and 1960s.

Punchcode is the compiled (UTF-8) form of it.

There is no compiler or interpreter publicly accessible at the moment because I am still working on it.

punchtape

START|
O-OO-|
OOOO-|
----O|
---O-|
----O|
-----|
----O|
---O-|
----O|
---OO|
----O|
----O|
----O|
O--OO|
----O|
-----|
----O|
-----|
OOOO-|
---OO|
-----|
-OO--|
---O-|
O---O|
OOO-O|
--OO-|
--O-O|
OO-OO|
O--O-|
O--OO|
OOO-O|
--OOO|
--O--|
O-O--|
---O-|
-O--O|
OO-OO|
OOOO-|
---OO|
-----|
O----|
--OO-|
O--OO|
---O-|
--OOO|
-OO-O|
O-O--|
---O-|
-O--O|
-O-OO|

punchcode

(This contains characters that a lot of web browsers and fonts dont display or display them in a way that is inconvenient for showing code. To combat this, all characters have been shifted 32 times byte-wise to show as basic latin characters.)

6>!"! !"!#!!!3! ! ># ,"1=&%;23='$4");># 0&3"'-4")+

Here is the original form of the code, if you are curious: