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

AWK, 38 bytes

{for(x=1ドル;x>1;0ドル=++i)x=x%2?1+x*3:x/2}1

Attempt This Online!

{for(x=1ドル; # x equals input
x>1; #
0ドル=++i) # increment output
x=x%2?1+x*3:x/2} # collatz
1 # print 0ドル

Answer 2

ArnoldC, 880 bytes

IT'S SHOWTIME
HEY CHRISTMAS TREE i
YOU SET US UP 0
HEY CHRISTMAS TREE l
YOU SET US UP 0
HEY CHRISTMAS TREE e
YOU SET US UP 0
HEY CHRISTMAS TREE c
YOU SET US UP 0
GET YOUR ASS TO MARS i
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
GET TO THE CHOPPER l
HERE IS MY INVITATION i
LET OFF SOME STEAM BENNET 1
ENOUGH TALK
STICK AROUND l
GET TO THE CHOPPER c
HERE IS MY INVITATION c
GET UP 1
ENOUGH TALK
GET TO THE CHOPPER e
HERE IS MY INVITATION i
I LET HIM GO 2
ENOUGH TALK
BECAUSE I'M GOING TO SAY PLEASE e
GET TO THE CHOPPER i
HERE IS MY INVITATION i
YOU'RE FIRED 3
GET UP 1
ENOUGH TALK
BULLSHIT
GET TO THE CHOPPER i
HERE IS MY INVITATION i
HE HAD TO SPLIT 2
ENOUGH TALK
YOU HAVE NO RESPECT FOR LOGIC
GET TO THE CHOPPER l
HERE IS MY INVITATION i
LET OFF SOME STEAM BENNET 1
ENOUGH TALK
CHILL
TALK TO THE HAND c
YOU HAVE BEEN TERMINATED

Try it online!

explained:

IT'S SHOWTIME #begin main
HEY [...]
 US UP 0 #variable declarations
GET YOUR ASS TO MARS i #assign result of method call to i
DO IT NOW
I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY
 #call method read integer
GET TO THE CHOPPER l #assign to l(oop)...
 HERE IS MY INVITATION i
 LET OFF SOME STEAM BENNET 1 #i>1?
ENOUGH TALK
STICK AROUND l #while l
 GET TO THE CHOPPER c #c++
 HERE IS MY INVITATION c
 GET UP 1
 ENOUGH TALK
 GET TO THE CHOPPER e #e=i%2
 HERE IS MY INVITATION i
 I LET HIM GO 2
 ENOUGH TALK
 BECAUSE I'M GOING TO SAY PLEASE e #if e==1
 GET TO THE CHOPPER i #i = i*3+1
 HERE IS MY INVITATION i
 YOU'RE FIRED 3
 GET UP 1
 ENOUGH TALK
 BULLSHIT #else
 GET TO THE CHOPPER i #i = i/2
 HERE IS MY INVITATION i
 HE HAD TO SPLIT 2
 ENOUGH TALK
 YOU HAVE NO RESPECT FOR LOGIC #endif
 GET TO THE CHOPPER l #l = i>1
 HERE IS MY INVITATION i
 LET OFF SOME STEAM BENNET 1
 ENOUGH TALK
CHILL #endwhile
TALK TO THE HAND c #print(c)
YOU HAVE BEEN TERMINATED #end main

Answer 3

SAKO, 83 bytes

PODPROGRAM:F(N)
I=0
1)I=I+1
D=MOD(N,2)
N=(×ばつN)/2+D
GDYN=1:2,INACZEJ1
2)F()=I
WROC

Uses the formula N=(×ばつN)/2+D where D = N mod 2 for calculating the next value in the sequence.
I don't believe this is the shortest solution, but I'm stuck and don't know how to make it shorter. (I'm probably missing something obvious.)

Full programme version, 92 bytes

CZYTAJ:N
I=0
1)I=I+1
D=MOD(N,2)
N=(×ばつN)/2+D
GDYN=1:2,INACZEJ1
2)DRUKUJ(9,0):I
STOP1
KONIEC

Reads from STDIN. For results above 10 digits long prints in E notation.

• Themoonisacheese: Is there a reason you're choosing not to use the subroutine version as your main answer? it's shorter and it's perfectly allowed to answer with functions
• Acrimoris: @Themoonisacheese Oh, thanks, I forgot about that.

Answer 4

Raku (Perl 6) (rakudo), 50 bytes

->$x {(my$n=$x,{$n=$n%2??3*$n+1!!$n/2}...2).elems}

Attempt This Online!

->$x # take arg
{(my$n=$x, # make mutable
{$n=$n%2??3*$n+1!!$n/2} # collatz
...2) # lazy list of each step
.elems} # number of steps

Answer 5

Axiom, 74 bytes

g(a)==(c:=0;repeat(a<=1=>break;c:=c+1;a rem 2=0=>(a:=a quo 2);a:=3*a+1);c)

ungolfed

gg(a)==
 c:=0
 repeat
 a<=1 =>break
 c:=c+1 
 a rem 2=0=>(a:=a quo 2)
 a:=3*a+1
 c

results

(3) -> [i,g(i)] for i in [2,16,5,7,1232456,123245677777777777777777777777777]
 Compiling function g with type PositiveInteger -> NonNegativeInteger
 (3)
 [[2,1], [16,4], [5,5], [7,16], [1232456,191],
 [123245677777777777777777777777777,572]]
 Type: Tuple List NonNegativeInteger

Answer 6

R, (削除) 57 (削除ここまで) 55 bytes

x=scan();n=0;while(x-1){x='if'(x%%2,3*x+1,x/2);n=n+1};n

Not much to say, uses a nice statement within the while loop, which should become 0 -> False only when x=1, similar to the check whether x is odd or even. This also uses the implicit conversion of 0->False and nonzero -> True.

Saved 2 bytes thanks to a trick by @Billywob used in this answer.

• JayCe: Abusing a built-in (F) saves 4 bytes - the other change is just a different way of doing the if, not golfier.

Answer 7

C#, 71 bytes

Assuming output is required as opposed to just a return

n=>{int i=0;while(n>1){n=n%2<1?n/2:n*3+1;i++;}System.Console.Write(i);}

Answer 8

Java (OpenJDK), 53 bytes

n->{int i=0;for(;n>1;i++)n=n%2<1?n/2:n*3+1;return i;}

Try it online!

Answer 9

Java 8, 53 bytes

i->{for(;i>1;)System.out.print(i=i&1>0?i=3*i+1:i/2);}

Another solution(Java 9)

i->IntStream.iterate(i,j->j&1>0?j*3+1:j/2).takeWhile(n->true);

Answer 10

TI-Basic, 47 bytes

Prompt A
0→B
While A-1
Aremainder(A+1,2_/2+(3A+1)remainder(A,2→A
B+1→B
End
B

Answer 11

Emojicode, 139 bytes

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

Try it online!

Answer 12

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 13

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 14

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 15

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 16

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 17

Ahead, 38 bytes

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

Try it online!

Answer 18

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 19

SmileBASIC, 54 bytes

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

Answer 20

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 21

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 22

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 23

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 24

Knight, 37 bytes

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

Try it online!

Answer 25

ibe, 68 bytes

adadaddsQakqafEmwskWafWmQsjWmesdWmqmwahQmrafQmwalqakwajQmeshQmwmqasE

explanation soon

Answer 26

Periodically, 73 bytes

yes i made this esolang recently, but it's not even good for golfing! so does it really matter?

H6I3Br2IBrO2Br3O2Ti[IKCI3SeF{OCONBrIFI}Fe{OCSiFI}CO3KI4AlO4FOI5BrCo]1I5Cl

explanation (this code is not valid)

H6 | initialize tape with 6 elements
I3Br2 | add 2 to vars[3]
IBr | add 1 to vars[4] 
O2Br3 | add 3 to vars[2]
O2Ti | get user input, set it to vars[2]
[ | do...
 IK | copy vars[0] to vars[1]
 CI3SeF | modulo vars[1] by 2
 { | if vars[1] is 1...
 OCON | multiply vars[0] by 3
 Br | add 1
 IFI | neutralize argument list so nothing messes up
 } | ...end
 Fe | apply logical NOT to vars[1]
 { | if vars[1] is 1...
 OCSi | divide vars[0] by 2
 FI | neutralize argument list
 } | ...end
 CO3K | copy vars[0] to vars[1]
 I4Al | set vars[1] to the boolean result of if vars[1] != 1
 O4FOI5Br | increase vars[5] by 1
 Co | reset argument stuff
]1 | ...while vars[1] is true
I5Cl | print the final result (vars[5])

Answer 27

Jalapeño, 21 bytes

%2?x{2*3+1/2§‽{2⇥>2,{2⇥C0↔

Explained

 # The "Colatz" chain
%2 # Input % 2
?x # If, Else
 {2 # If truthy (odd)
 *3+1 # Input *3 + 1
 /2 # If falsy (even), return input / 2
§ # Chain seperator
‽ # While, with input as initial state
 {2⇥>2 # The Last element of state is > 2
 ,{2 # Append to the state... (Returns state , ...)
 ⇥C0 # Execute the first chain (Colatz) on the last element
↔ # Return the length of the final state

Hex-Dump of Bytecode

 0 1 2 3 4 5 6 7 8 9 A B C D E F
0000: 54 32 a1 c6 52 33 50 31 53 32 0a a2 c6 dc 5b 32 
0010: 29 c6 dc c0 d6 

Try it Online!

All test cases!

Answer 28

Swift 6, 40 bytes

let e={0ドル<2 ?0:e(0ドル%2<1 ?0ドル/2:0ドル*3+1)+1}

Answer 29

Bespoke, 269 bytes

take N
a N value2K divides cleanly by twos;else,we actually triple it,adding ones
notice with one,it loops
reaching one happened generally;this is Collatzs conjecture
question:will it always continue looping it?nobody is sure
iterated counting assumes one is a lonely N

Uses the formula \$\frac{6^{n \% 2} \times n}{2} + (n \% 2)\$ to calculate the next number in the sequence, and counts along until \$n\$ is 1. (This turned out to be the same byte count as a naive approach with CONTROL IF/CONTROL OTHERWISE, but I liked these word lengths better.)