# Collatz Conjecture (OEIS A006577)

This is the Collatz Conjecture (OEIS A006577):

• 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 * 260, 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.

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


## C, 70 69 chars

Quite simple, no tricks.

a;
main(b){
for(scanf("%d",&b);b-1;b=b%2?b*3+1:b/2)a++;
printf("%d",a);
}


{i::0;{x>1}{i+:1;$[x mod 2;1+3*x;(_)x%2]}\x;i}  • 32 bytes with (#)1_(1<){(1+3*x;x%2)0=x mod 2}\  – mkst Oct 26, 2017 at 22:17 # C++ (51 48) This is a recursive function that does this; input reading comes separately. int c(n){return n==1?0:1+(n%2?c(n*3+1):c(n/2));}  I'm sure I can do some sort of "and/or" trick with the == 0 stuff, but I have no idea how. • You could remove the ==0 and swap the sides of the conditional Nov 30, 2013 at 15:30 • Also, no need to handle n==1 because I specified in the question that the number is always greater than 1 Nov 30, 2013 at 15:31 • The problem is that n==1 is the base recursion case. Putting n==2 there wouldn't improve the score any. Nov 30, 2013 at 17:57 • Ah, then you could just replace it with this: return~-n? and swap the conditional sides Nov 30, 2013 at 23:20 • .n==1==n<2. Apr 18, 2016 at 16:53 # ~-~! (No Comment) - 71 53 This language is obviously not the best for golfing since it lacks a large amount of native functionality, but that's the beauty of it. '=|*;~~[*,~~~-~]*/~~|:''=|'''==~[*]'''='&''':''&*+~|:  First, set ''' to your input. The function '' can then be called with % as it's input and will return the answer, like so: '''=~~~~~:''&%: This will return ~~~~~. It actually works for n==1 (it loops forever with n==0). As always with this language, untested. # JavaScript (ES6) - 29 Characters f=x=>x>1?f(x%2?x*3+1:x/2)+1:0  Creates a function f which accepts a single argument and returns the number of iterations. # JavaScript - 31 Characters for(c=0;n>1;n=n%2?n*3+1:n/2)++c  Assumes that the input is in the variable n and creates a variable c which contains the number of iterations (and will also output c to the console as its the last command). • 28 bytes Jan 24, 2019 at 12:23 # Perl 6, 40 bytes Recursive function method, as per Valentin CLEMENT and daniero: 40 characters sub f(\n){n>1&&1+f n%2??3*n+1!!n/2}(get)  Lazy list method: 32 characters +(get,{$_%2??$_*3+1!!$_/2}...^1)


# Ruby, 35 bytes

f=->n{n<2?0:1+f[n*3/(6-5*w=n%2)+w]}


Try it online!

### How it works

Instead of getting the 2 values and choosing one, multiply by 3, divide by 1 if odd, or 6 if even, and then add n modulo 2.

• -2 bytes May 3, 2022 at 3:50

# MathGolf, 7 bytes

kÅ■┐▲î


Don't get fooled, there's a non-breaking space at the end of the program.

Try it online!

## Explanation

k        Read input as integer
Å       Start a block of length 2
■      Map TOS to the next item in the collatz sequence
┐     Push TOS-1 without popping
▲    Do block while TOS is true
î   Push the length of the last loop
Discard everything but top of stack


# MathGolf, 14 bytes (no built-ins, provided by JoKing)

{_¥¿É3*)½┐}▲;î


## Explanation

{               Start block of arbitrary length
_              Duplicate TOS
¥             Modulo 2
¿            If-else (works with TOS which is 0 or 1 based on evenness)
É3*)        If true, multiply TOS by 3 and increment
½       Otherwise halve TOS
┐      Push TOS-1 (making the loop end when TOS == 1)
}▲    End block, making it a do-while-true with pop
î  Print the loop counter of the previous loop (1-based)


Ideally, this solution could become 13 bytes, since it's not neccessary to have the ending of the block be explicit when the loop type instruction comes right after. I'll see when I get around to coding implicit block ending when loop type is present.

Try it online!

• This is 12 bytes if you don't use the collatz operator
– Jo King
Oct 6, 2018 at 8:39
• Nice solution! I'll have to analyze a bit before I understand it completely. I wrote this solution when the language was still really new, there are a bunch of new features now
– maxb
Oct 6, 2018 at 9:25
• @JoKing I've looked your solution over, and I might have to clarify the documentation, ∙ (documented as "triplicate TOS") does not push TOS*3, but instead pushes TOS 3 times. Your solution gives the correct input for powers of 2, but fails for e.g. input 7.
– maxb
Nov 15, 2018 at 8:15
• Lol, my bad. In that case, it would be 14 bytes
– Jo King
Nov 15, 2018 at 9:14

# C (gcc), 43 33 bytes

f(x){x=~-x?f(x&1?3*x+1:x/2)+1:0;}


Try it online!

# BitCycle-u, 90 bytes

 ~  ~!
?v C/v
v<   <
A\\ B^
>/\/C =v
Cvv  <
v~v/
>   ^
v =
>> >>^
\~~~
~v~^
^ + ~


Try it online! Or, watch it in action here.

### Algorithm

The main loop starts with the current number $$\n\$$ in unary in the A collector. We divide the number by 2, splitting off two bits at a time; one of the halves, $$\\lfloor \frac n 2 \rfloor\$$, goes into the uppermost C collector; the other half goes into the middle C collector; and the remainder, $$\n\text{ mod }2\$$, goes into the bottom C collector.

Once the number is completely divided up in this way, the C collectors open.

• The top C collector sends a 1 to the sink at the top right, adding 1 to the output, and sends all of its bits back into A.
• If the bottom C collector is empty (i.e. $$\n\text{ mod }2 = 0\$$, i.e. $$\n\$$ was even), the first bit from the middle collector hits the bottommost switch = and activates it pointing right, which discards the bits. This leaves A with just the $$\\lfloor\frac n 2\rfloor\$$ bits it got from the top C collector: $$\n\text{ even}\to n/2\$$.
• If the bottom C collector contains a 1 bit (i.e. $$\n\text{ mod }2 = 1\$$, i.e. $$\n\$$ was odd), a negated copy of it hits the bottommost switch and activates it pointing left. This sends the bits from the bottom and middle C collectors into the big collection of dupnegs ~ at the bottom, which makes five copies of its input and discards one bit. All the copies are then sent back into A: $$\n\text{ odd}\to \lfloor\frac n 2\rfloor + 5\left( \lfloor\frac n 2\rfloor + 1\right) - 1 = 6\lfloor\frac n 2\rfloor + 3 + 1 = 3n + 1\$$.

This whole process repeats until $$\n=1\$$, at which point the two halves are 0; this means the only C collector with data is the bottommost one that holds the remainder. The remainder bit is directed up to the uppermost switch =. Normally, this switch would have been activated by the bits from the middle C collector already, and the remainder bit would follow them into the 5-times circuitry. But since the middle C collector is empty, the remainder bit passes through the switch and continues northward off the playfield. Since there are no bits remaining on the playfield, the program halts and displays the number of steps taken.

# ><>, 28 bytes

:1=?v::2%?v2,
+c0.\l1-n;\3*1


This takes input from the stack, computes the different steps on the stack, then returns its size when 1 is reached.

Improved version by JoKing, 24 bytes :

:1=?\::2%b$.2, 3*1+\~ln;  • That is one of the most beautiful snippets of ><> I have ever seen. Apr 14, 2016 at 15:29 • Hu, is it? Thanks ! You might like my FizzBuzz one then, it's got a few control-flow tricks I was proud of. Apr 14, 2016 at 15:56 • Given the input can't be zero, you don't need to do the is one check when doing triple plus one, and therefore skip the jump entirely, saving three bytes. Then one more byte through shortening the output and using a jump instead of a conditional. Try it online! – Jo King Nov 14, 2021 at 22:24 • @JoKing thanks, I appreciated this occasion to jog my brain on some ><> ! I still remember your invitation to come golf some more on code.golf by the way, I might find some time to do so soon ! :) Nov 22, 2021 at 15:24 # x86 machine code, 15 bytes #### xxd -g1: 00000000: 99 42 8d 4c 40 01 d1 e8 0f 42 c1 75 f4 4a c3 [email protected].  #### Commented assembly (NASM syntax):  [bits 32] global collatz ; input: eax, assumed positive and > 1 ; output: edx ; clobbers: eax, ecx, edx collatz: cdq ; count = 0 (abuses eax > 1) .Lloop: inc edx ; increment count lea ecx, [eax+2*eax+1] ; tmp = 3*n + 1 shr eax, 1 ; n = n / 2, sets flags cmovc eax, ecx ; swap with 3n+1 if it was originally odd (does not set flags) jnz .Lloop ; shr also sets ZF if the shr result was zero, end condition dec edx ; Correct the off by one ret ; return  Try it online! (converted to GAS Intel syntax and wrapped in C++) ### Notes The way this works is by using shr magic, allowing me to calculate n/2 and also test if n was originally odd (CF=1) or originally 1 (ZF=1). Unfortunately, this results in an off by one since it will run when n == 1, but it is correctable via a simple dec. Note that while this is larger than the other x86 solution, the other solution is a snippet, not a complete function, and it doesn't even count the steps, only calculating the sequence. If that version were to count the steps, while it would be more efficient, it would be larger because the bsr complicates the bookkeeping, unless I can be proven otherwise. • bsf returns the count by itself, so you can just add that to the total count, but it's true that the other answer doesn't count at all. Feb 18, 2022 at 9:29 # Julia, 54 chars f(n,i)=n==1 ? i : n%2==0 ? f(n/2,i+=1) : f(n*3+1,i+=1)  Try it online! # Julia, 45 chars >(n,i=0)=n<2 ? i : n%2<1 ? n/2>i+1 : 3n+1>i+1  Try it online! Thanks to the brilliant suggestion by MarcMush! • 45 bytes Feb 15, 2022 at 10:06 • I'm overloading the > function, and since it has lower precendence than +, you don't need parenthesis Feb 15, 2022 at 10:10 • if you haven't already, check out codegolf.stackexchange.com/questions/24407/… Feb 15, 2022 at 10:11 • you can avoid parenthesis altogether and save five more bytes Try it online! Feb 17, 2022 at 18:57 • @amelies no, because you're supposed to initialize the variable in the function, not ask the user to do it. This is more or less this forbidden loophole Feb 17, 2022 at 21:32 # Pyth 23byte J0WtQ=Q@,/Q2h*3QQ=JhJ;J  • Welcome to Code Golf, and nice answer! Aug 21, 2022 at 1:54 # Acc!!, 12775 70 bytes -5 bytes thanks to Mukundan314 Count u while N { u } Count i while _-1 { _/2+_%2*(5*_/2+2) Write 49 }  The program takes input and produces output in unary. Try it online! (Here's a decimal I/O version in 209 bytes.) ### With comments The input method technically takes advantage of undefined behavior: the official implementation of Acc!! adds a newline character to the end of each line of input. # Read input in unary Count u while N { # Increment u from 0 while not EOF u # Set accumulator to u } # For a unary number X, the loop will run X+1 times (including the # trailing newline); because the loop variable starts at 0, this sets # the accumulator to X # Main loop Count i while _-1 { # Increment i from 0 while accumulator is not equal to 1 _/2+_%2*(5*_/2+2) # Apply one step of Collatz function to accumulator Write 49 # Write "1" to output }  The expression _/2+_%2*(5*_/2+2) boils down to _/2, if _%2 is 0 _/2 + (5*_)/2 + 2, if _%2 is 1  This is integer division, so the latter case comes out to _/2 + 2*_ + _/2 + 2 = 2*_ + (_/2)*2 + 2 = 2*_ + _ + 1 = 3*_ + 1  • 70 bytes Apr 17 at 16:38 ## newLISP - 94 chars Strangely similar to Valentin's Scheme answer... :) I'm let down here by verbosity of the language but there's a bitshift division which appears to work... (let(f(fn(x)(cond((= x 1)0)((odd? x)(++(f(++(* 3 x)))))(1(++(f(>> x)))))))(f(int(read-line))))  # Python (73): Can probably be golfed a heck of a lot more. i=0 while 1: i+=1;j=i;k=0 while j!=1:j=(j/2,j*3+1)[j%2];k+=1 print i,k  ## Haskell 73 Bytes 73 Chars r n |even n=nquot2 |otherwise=3*n+1 c=length.takeWhile(/=1).iterate r  • otherwise in golf??? Use 1>0 May 10, 2014 at 7:32 • You can save another 2 chars with takeWhile(>1) and div. – sjy Sep 22, 2014 at 2:51 ## Fish (33 chars including whitespace, 26 without) :2%?v:2, >:1=?v >:3*1+^;nl~<  The whitespace is necessary for it to function, as ><> is a 2D language. Example run: $ python3 fish.py collatz.fish -v 176
18


# K, 24 bytes

#1_(1<){(x%2;1+3*x)x!2}\


With test cases:

  (#1_(1<){(x%2;1+3*x)x!2}\)'2 16 5 7
1 4 5 16


This uses a bit of a cute trick to avoid conditionals- (x%2;1+3*x) builds a list of the potential next term and then the parity calculated by x!2 indexes into that list. Otherwise it's a straightforward application of the "do while" form of \, given the tacit predicate (1<) (while greater than 1) as a stopping condition:

  (1<){(x%2;1+3*x)x!2}\5
5 16 8 4 2 1


The example output indicates that we need to drop the first (1_) of this sequence before taking the count (#). This is slightly shorter than taking the count and then subtracting one.

# Befunge, 42 40 bytes

Surprisingly short to be an esolang! I thank @Sok for showing how to avoid one extra branching in his answer. Saved 2 bytes after a complete rewriting of the code.

0&>\1+\:2/\:3v
.$<v_v#%2\+1*<@ !|>\>$:1


1&>:2%v>2v
^\+1*3_^ /
>+v  v1:<
^1\#\_$.@  Shold be compatible with both Befunge 93 and Befunge 98. Interpretor available here. There is no need for a trailing white space after @, so I count it as 42. However, 2D languages are often counted by their bounding box. • We count all answers by their length in bytes. If you don't need the trailing space, leave it off and save yourself a byte. Bounding box doesn't matter here. – user45941 Apr 18, 2016 at 5:53 • Glad to have helped :o) – Sok May 5, 2016 at 14:40 • If you try to pop a value from the stack, and there aren't any values on the stack, a 0 is popped. Therefore, the stack is filled with an infinite amount of 0s for practical purposes. Because of this, you don't need the 0 at the beginning of your program, letting you shift over each line to save a byte. I can suggest an edit to show you what I mean, if you want. Dec 5, 2016 at 17:58 # Haskell, 43 Bytes c 1=0 c x|odd x=1+c(3*x+1)|1<2=1+c(xdiv2)  Usage: c 7-> 16 • What's "Haskell 2"? – user344 Dec 6, 2016 at 23:14 • @nyuszika7h: a typo – nimi Dec 6, 2016 at 23:14 # Python 2, 595755 54 bytes i=0;n=input() while~-n:n=[n/2,n*3+1][n%2];i+=1 print i  • You can remove the indentation and newline for the while loop, while n>1:n=.... works the same. May 4, 2016 at 14:27 • @EᴀsᴛᴇʀʟʏIʀᴋ Thanks, I thought that didn't work when there are multiple statements inside. – user344 May 4, 2016 at 18:45 • It does work, as long as you don't have any other "indent required" statements such as another loop. Semicolons work fine for plain statements though. May 4, 2016 at 20:03 • Can't you remove greater than 0, as it can only be 1 or 0? Dec 6, 2016 at 0:29 • Since n can't be 0, can you do while~-n: to save a byte? Dec 7, 2016 at 5:34 # Clojure, 60 bytes (fn c[n](if(= n 1)0(inc(c(if(even? n)(/ n 2)(+(* n 3)1))))))  Pretty standard. Recursive function that recurses when n isn't equal to one. Each iteration, one is added to the accumulator via inc. While this uses unoptimized recursion, I'm currently testing to see when it fails. It's at 1711000000, and is still going. The highest number of steps I've seen so far is 1008, so I don't expect it to fail anytime soon. Pregolfed: (defn collatz-conj [n] (if (= n 1) 0 ; Base case (inc ; Add one to step (collatz-conj ; Recurse (if (even? n) ; The rest should be be self-explanatory (/ n 2) (+ (* n 3) 1))))))  • You can save 1 byte by using odd? instead of even?. You can save another byte by replacing (inc(...)) with (+(...)1) Jan 9, 2018 at 3:55 # TCL 8.5 (71 70 68) (67) TCL has no real chance of ever winning, but it is a fun way to oil the machine: proc c x {while $x>1 {set x [expr x%2?3*x+1:x/2];incr k};set k}  formatted for readability: proc c x { while {x>1} { set x [expr x%2 ? 3*x+1 : x/2] incr k } set k }  Edits: many suggestions (inspired) by sergiol. I guess the answer is more theirs than mine, by now :-) • is all the whitespace really neccessary? Nov 9, 2013 at 20:06 • @JanDvorak I think it is, in TCL. Nov 9, 2013 at 20:08 • Didactic post to make me now that applying incr to an undefined variable interprets it as 0 and then does the increment! Jan 19, 2017 at 1:44 • You can shave one character off if you replace while {x>1} by while$x>1 Apr 4, 2017 at 9:18 • @RolazaroAzeveires: You are loosing to answers which implement it as a function. I purpose sthg like: proc c x {while \$x>1 {set x [expr $x%2?3*$x+1:$x/2];incr k};set k} — 67. demo: rextester.com/LLUS24241 Apr 5, 2017 at 9:36 # Game Maker Language, 6361 60 bytes Make script/function c with this code and compile with uninitialized variables as 0: a=argument0while(a>1){i++if i mod 2a=a*3+1else a/=2}return i  Call it with c(any number) and it will return how many times it took to become 1. # Emacs/Common Lisp, 61 bytes (defun f(n)(if(= 1 n)0(1+(f(if(oddp n)(1+(* 3 n))(/ n 2))))))  alternatively: (defun f(n)(if(= 1 n)0(1+(f(if(oddp n)(+ n n n 1)(/ n 2))))))  # Python 2, 38 37 bytes f=lambda n:n<3or-~f([n/2,n*3+1][n%2])  Thanks to @user84207 for a suggestion that saved 1 byte! Note that this returns True instead of 1. Try it online! • you could save one byte by using n<1or instead of n>1and Jan 9, 2018 at 4:13 • @user84207 n<1or doesn't work (n is never less than 1) and n<2or would be off by one, but n<3or works just fine. Since 0 == False and 1 == True in Python, returning Booleans is allowed by default. Jan 9, 2018 at 14:01 # Befunge-93, 29 bytes &<\+1\/2+*%2:+2*5:_$#-.#1@#:\$


Try it online!

A nice and concise one-liner. This uses the formula (n+(n*5+2)*(n*5%2))/2 to calculate the next number in the series.

# Emojicode, 157 bytes

🐖🎅🏿➡️🔡🍇🍮a🐕🍮c 0🔁▶️a 1🍇🍊😛🚮a 2 0🍇🍮a➗a 2🍉🍓🍇🍮a➕✖️a 3 1🍉🍮c➕c 1🍉🍎🔡c 10🍉


Try it online!

Explanation:

🐋🚂🍇
🐖🎅🏿➡️🔡🍇
🍮a🐕      👴 input integer variable 'a'
🍮c 0         👴 counter variable
🔁▶️a 1🍇      👴 loop while number isn’t 1
🍊😛🚮a 2 0🍇     👴 if number is even
🍮a➗a 2       👴 divide number by 2
🍉
🍓🍇      👴 else
🍮a➕✖️a 3 1   👴 multiply by 3 and add 1
🍉
🍮c➕c 1     👴 increment counter
🍉
🍎🔡c 10   👴 return final count as string
🍉
🍉
🏁🍇
😀🎅🏿 16
🍉