# 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


## 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 – John Dvorak 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  # 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  Original answer: 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. – Mego Apr 18 '16 at 5:53
• Glad to have helped :o) – Sok May 5 '16 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. – MildlyMilquetoast Dec 5 '16 at 17:58

# Julia, 29 27 bytes

!n=n>1&&1+!(n%2>0?3n+1:n/2)


I can't seem to compile Julia 0.1 on my machine, so there's a chance this is non-competing.

Try it online!

# 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) – user84207 Jan 9 '18 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? – John Dvorak Nov 9 '13 at 20:06 • @JanDvorak I think it is, in TCL. – Doorknob Nov 9 '13 at 20:08 • @JanDvorak Yes, as far as I know. Say, trying 'while{x>1}' results in the error 'invalid command name "while{7>1}"' (executing 'tclsh collatz-conjecture.tcl 7'). That is, the interpreter substitutes x, and then assumes the resulting string to be a command, and it is quite liberal to what may be a command name. – user7795 Nov 9 '13 at 20:17 • Didactic post to make me now that applying incr to an undefined variable interprets it as 0 and then does the increment! – sergiol Jan 19 '17 at 1:44 • @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 – sergiol Apr 5 '17 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. ## 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))))))  # 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 – user84207 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. – Dennis 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)


# Jelly, 10 bytes

×3‘ƊHḂ?Ƭi2


Try it online!

### How it works

×3‘ƊHḂ?Ƭi2    Main link (monad). Input: integer >= 2
?       Create a "ternary-if" function:
Ḃ          If the input is odd,
×3‘Ɗ            compute 3*n+1;
H           otherwise, halve it.
Ƭ      Repeat until results are not unique; collect all results
i2    Find one-based index of 2


Example: The result of ...Ƭ for input 5 is [5, 16, 8, 4, 2, 1]. The one-based index of 1 is 6, which is 1 higher than expected. So we choose the index of 2 (which is guaranteed to come right before 1) instead.

# 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? – ASCII-only 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 – Wisław 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.) – Kevin Cruijssen Jan 28 '19 at 14:32
• Thanks @KevinCruijssen! I am still bad at taking advantage of implicit input :-) – Wisław Jan 28 '19 at 15:00
• 14 bytes – Zylviij 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


# 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... – Sp3000 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. – BobTheAwesome Mar 15 '15 at 2:04

# Pyth 2723 22 chars

W>Q1=hZ=Q?h*Q3%Q2/Q2)Z


online

Pyth is much newer than the challenge and therefore won't count as a winning candidate

• Btw. W>Q1 is the same thing as WtQ – Jakube May 29 '15 at 9:05
• I didn't even look at the date ;) And thanks. – gcq May 29 '15 at 9:06
• If your interested in a 18 bytes solution: fq1=Q?h*Q3%Q2/Q2 1 gives 18 bytes. And I'm sure you can golf this even further. – Jakube May 29 '15 at 9:07
• The usage of f...1 not really documented (at least not good). It basically means: "find the first number >= 1, that satisfies ..." – Jakube May 29 '15 at 9:12
• That's good to know, tried to find that on the docs but no luck – gcq May 30 '15 at 20:03

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

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

• That is one of the most beautiful snippets of ><> I have ever seen. – SE - stop firing the good guys 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. – Aaron Apr 14 '16 at 15:56

# Oracle SQL 11.2, 122 bytes

WITH v(n,i)AS(SELECT:1,0 FROM DUAL UNION ALL SELECT DECODE(MOD(n,2),0,n/2,n*3+1),i+1 FROM v WHERE n>1)SELECT MAX(i)FROM v;


Un-golfed :

WITH v(n,i)AS   -- Recursive view, n=>current value, i=>iterations count
(
SELECT :1,0 FROM DUAL -- Initialize with parameter and 0 iteration count
UNION ALL
SELECT DECODE(MOD(n,2),0,n/2,n*3+1),i+1 -- Compute the next value
FROM   v WHERE n>1 -- End when it reaches 1
)
SELECT MAX(i)FROM v -- Return only the last iteration count


From user perspective, Mathcad is effectively a 2D whiteboard, with expressions evaluated from left-to-right,top-to-bottom. Mathcad does not support a conventional "text" input, but instead makes use of a combination of text and special keys / toolbar / menu items to insert an expression, text, plot or component. For example, type ":" to enter the definition operator (shown on screen as ":=") or "ctl-]" to enter the while loop operator (inclusive of placeholders for the controlling condition and one body expression). What you see in the image above is exactly what appears on the user interface and as "typed" in.

For golfing purposes, the "byte" count is the equivalent number of keyboard operations required to enter an expression.

• Keyboard operations required to enter an expression please? – CalculatorFeline Apr 18 '16 at 17:00
• Answer Part 1: Tricky. Becomes somewhat of a habit after a short time and I have to look at what I'm doing to answer this one ... ":" to enter the definition operator (:=), "]" for a programming line (black vertical bar after the :=), "ctl-#" for the while loop operator (see text), "3n" for implicit multiplication of n by 3, "shft-[" for local definition operator, "ctl-/" for in-line division operator, single-quote for balanced parentheses (context dependent). After a while, a user develops their own method of keyboard and mouse editing, which means the entry sequence can be different. – Stuart Bruff Apr 18 '16 at 17:53

# Befunge 93, 37 bytes

Try it Online!

&>:1-|
\@#-1<+2_.#
v#%2:<+1*3:_
<v/2:


Explanation:

&         Take integer input
>:1-|    If the top of the stack is 1, go to the 2nd line.
Else, go the third.

----------------------------------------------

\  -1<+2_      The top of the stack is 1, which becomes the counter for
the stack size. If the second-to-the-top of the stack is
non-zero, consume that value and increment the counter by 1.

@       .     If the second-to-the-top of the stack is 0, i.e. there are
no elements besides the counter, output the counter and
terminate the program.

----------------------------------------------

v#%2:<     _    The top of the stack is non-zero. Check if the top of
the stack is divisible by 2, and execute 1 of the
following accordingly:

+1*3:     The top of the stack (a) is odd, so push 3a + 1,
and check the top mod 2 again.

<v/2:           The top of the stack (a) is even, so push a / 2,
and check if the top is 1 again.


Like other programs, this pushes each iteration onto the stack until the top is 1, and outputs the stack size - 1.

I was able to make this program shorter by not testing if the top was 1, if the previous iteration was odd. Also, in counting the stack size, I used the fact that the top of the stack will always be 1.

# 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. – Rɪᴋᴇʀ May 4 '16 at 14:27
• @EᴀsᴛᴇʀʟʏIʀᴋ Thanks, I thought that didn't work when there are multiple statements inside. – nyuszika7h May 4 '16 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. – Rɪᴋᴇʀ May 4 '16 at 20:03
• Can't you remove greater than 0, as it can only be 1 or 0? – Destructible Lemon Dec 6 '16 at 0:29
• Since n can't be 0, can you do while~-n: to save a byte? – Destructible Lemon Dec 7 '16 at 5:34

# Clojure, 77 bytes

#(loop[x % a 0](if(= x 1)a(recur(if(=(mod x 2)0)(/ x 2)(+(* x 3)1))(inc a))))


Defines an anonymous function. Usage is like so:

(#(...) {num})


Ungolfed:

(defn collatz [n]
(loop [x n
a 0]
(if (= x 1) a
(recur (if (= (mod x 2) 0) (/ x 2) (+ (* x 3) 1)) (inc a)))))


## C, 38 bytes

g(v){return v^1?1+g(v&1?v*3+1:v/2):0;}