# 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


# 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 '19 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)  # ><>, 27 26 23 bytes \ln; \::2%:@5*1+2,*+:2=?  Like the other ><> answers, this builds the sequence on the stack. Once the sequence reaches 2, the size of the stack is the number of steps taken. Thanks to @Hohmannfan, saved 3 bytes by a very clever method of computing the next value directly. The formula used to calculate the next value in the sequence is: $$f(n)=n\cdot\frac{5(n\bmod2)+1}{2}+(n\bmod2)$$ The fraction maps even numbers to 0.5, and odd numbers to 3. Multiplying by n and adding n%2 completes the calculation - no need to choose the next value at all! Edit 2: Here's the pre-@Hohmannfan version: \ln; \:::3*1+@2,@2%?$~:2=?


The trick here is that both 3n+1 and n/2 are computed at each step in the sequence, and the one to be dropped from the sequence is chosen afterwards. This means that the code doesn't need to branch until 1 is reached, and the calculation of the sequence can live on one line of code.

Edit: Golfed off another character after realising that the only positive integer that can lead to 1 is 2. As the output of the program doesn't matter for input < 2, the sequence generation can end when 2 is reached, leaving the stack size being the exact number of steps required.

Previouser version:

\~ln;
\:::3*1+@2,@2%?$~:1=?  • You can golf it to 23 if you unbranch the second line even more: \::2%:@5*1+2,*+:2=? Dec 14 '16 at 1:04 # 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. ## 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))))  ## 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 '14 at 7:32 • You can save another 2 chars with takeWhile(>1) and div. – sjy Sep 22 '14 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:<

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

## Alice, 26 bytes, non-competing

/2:k@
.i#o3*hk
^d/.2%.j.t$ Try it online! ### Explanation This makes use of Alice's "jump and return" commands which allow you to implement subroutines. They're not at all separately scoped or otherwise encapsulated and nothing is stopping you from leaving the "subroutine", but if you want you can basically use them to jump to a different place in the code to do whatever you need and then continue where you left off. I'm using this to choose between two different "subroutines" depending on the parity of the current value to either halve it or triple and increment it. To count the number of steps, we simply make a copy of the value at each step and check the stack depth at the end. / Reflect to SE. Switch to Ordinal. i Read the input as a string. / Reflect to E. Switch to Cardinal. . Duplicate the input. 2% Take the current value modulo 2 to get its parity. . Duplicate it. So for even inputs we've got (0, 0) on top of the stack and for odd inputs we've got (1,1). j Use the top two values to jump to the specified point on the grid. That's either the top left corner, or the cell containing the i. Using j also pushes the original position of the IP (the cell containing j in this case) to a separate return address stack, so we can return here later. Note that the IP will move before executing the first command. Subroutine for even values: 2: Divide by 2. k Pop an address from the return stack and jump back there (i.e. to the j). Subroutine for odd values: # Skip the next command (the 'o' is there for a later part of the code). 3* Multiply by 3. h Increment. k Pop an address from the return stack and jump back there (i.e. to the j). Either way, we continue after the j: . Duplicate the new value. t Decrement it, to get a 0 if we've reached 1.$     Skip the next value if the result was 0.

This part is run if the current value wasn't 1 yet:

^     Send the IP north.
.     Duplicate the current value to increase the stack depth.
/     Reflect to SW. Switch to Ordinal.
Immediately reflect off the left boundary and move SE.
i     Try to read more input, but this just pushes an empty string.
However, the next command will be the duplication . which tries to
duplicate an integer, so this empty string is immediately discarded.
After that we start the next iteration of the loop.

This part is run once the value reaches 1:

d     Push the stack depth.
/     Reflect to SE. Switch to Ordinal.
Immediately reflect off the bottom boundary and move NE.
o     Implicitly convert the stack depth to a string and print it.
@     Terminate the program.


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


# Acc!!, 127 75 bytes

Count u while N/49 {
_+1
}
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.)

# Read input in unary
Count u while N/49 {   # Increment u from 0 while input character is >= "1"
_+1                  # Add one to accumulator
}

# 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


# 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 '18 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 '18 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.

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

# 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
🍉


# MATL, 21 16 bytes

Saved 5 bytes thanks to Luis Mendo! I didn't know while had a finally statement that could be used to get the iteration index. Keeping track of the number of iterations took a lot of bytes in my original submission.

to?3*Q}2/]tq}x@


Try it online!

### Explanation:

t                % grab input implicitly and duplicate it.
% while ...
o?                % the parity is 1 (i.e. the number is odd
3*Q              % multiply it by 3 and increment it
}                % else
2/               % divide it by 2
]                % end if
tq               % Duplicate the current value and decrement it
}                 % Continue loop if this value is not zero (i.e. the current value is >1
x                 % Else, delete the current value (the 0)
@                 % And output the "while index" (i.e. the number of iterations)


# 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 '18 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 '18 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 '18 at 8:15
• Lol, my bad. In that case, it would be 14 bytes
– Jo King
Nov 15 '18 at 9:14

# 05AB1E, 16 15 bytes

-1 byte thanks to Kevin Cruijssen

[Éi3*>ë2÷}¼Ð#]¾


Try it online!

## Explanation

                  # Implicit input: integer n
[              ]  # Infinite loop
i       }      # if:
É               # n is odd
3*>           # compute 3n+1
ë          # else:
2÷       # compute n//2
¼     # increment counter variable
Ð    # Triplicate
#   # Break loop if n = 1
¾ # output counter variable

• wait. why does halve not work? floating point errors, i guess? Jan 19 '19 at 1:19
• yup, it turns integers into floats and I dont see a way to implicitly turn it into an integer again after halving Jan 19 '19 at 1:30
• You can save a byte removing the first D and changing the second D to Ð (in the first iteration it will implicitly use the input twice). (And you might want to change n/2 to n//2 or n integer-divided by 2 in your explanation to make it clear you're integer-dividing.) Jan 28 '19 at 14:32
• Thanks @KevinCruijssen! I am still bad at taking advantage of implicit input :-) Jan 28 '19 at 15:00
• 14 bytes Apr 30 '19 at 19:10

# Aceto, 33 bytes

&)
(I2/(I)&
+3_!
1*2%
i@d|(
rd1=p


### Explanation:

i
r


Set a catch point, duplicate the number and check if it's 1, if so, we mirror horizontally (meaning we end up on the ( next to the |):

 @ |
d1=


Duplicate the value again, check if it's divisible by 2, if so, we mirror vertically (ending up on the 2 above):

  _!
2%


Otherwise, multiply by 3, add 1, go one stack to the left, increment the number there (initially zero), go back to the original stack, and raise (jumping back to the catch point):

&)
(I
+3
1*


If it was divisible, we divide the number by two, and again increment the stack to the left and jump to the catch point:

  2/(I)&


When the number is 1 after jumping to the catch point, we go to the left stack and print that number (and exit):

    (
p


# Forth (gforth), 71 bytes

: f begin dup 2 mod if 3 * 1+ else 2/ then dup dup 1 = until depth 1- ;


Try it online!

Uses an until loop, and computes stack depth -1.

# Forth (gforth), 76 bytes

: f dup dup 1 = if 0 else 2 mod if 3 * 1+ else 2/ then dup recurse 1+ then ;


Try it online!

A recursive function.

# ><>, 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 '16 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 '16 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 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 at 15:24

# Java (136)

public class C {public static void main(String[] a) {int i=27,c=0;while(i!=1;{c++;if(i%2==0)i/=2;else i=3*i+1;}System.out.println(c);}}


Just change the value of i to the input. For 27, it prints 111 to the console.

Whitespace view:

public class C {
public static void main(String[] a) {
int i=27,c=0;
while(i!=1) {
c++;
if(i%2==0)
i/=2;
else
i=3*i+1;
}
System.out.println(c);
}
}


I know it isn't the shortest, but I figured I'd give it a whirl. Any suggestions would be appreciated. ;)

I have to say I'm a little envious of all those who know the short languages. I'd love to see this done in Brainf**k.

# 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


# This Programming Language, 59

v>v>_1=?v_2%?v2/  v
}0"     >~"i;>3*1+v
>^>^          "+1"<


Not the shortest, but an interesting program nonetheless.

• If this is anything like ><>, that's a lot of whitespace that could be golfed out... Mar 15 '15 at 1:46
• I wrote this program with a headache and I'm not really in the mood to golf it right now. Mar 15 '15 at 2:04