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

~-~! (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.

Answer 2

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

Answer 3

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)

Answer 4

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.

Answer 5

C (gcc), 43 33 bytes

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

Try it online!

Answer 6

><>, 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=?

Answer 7

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.

Answer 8

><>, 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;

Answer 9

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.

Answer 10

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!

Answer 11

Julia 0.6, 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!

Answer 12

Haskell, 39 38 bytes

saved 1 byte thanks to DLosc

f 2=1
f n=1+f(cycle[div n 2,n*3+1]!!n)

Attempt This Online!

Answer 13

Pyth 23byte

J0WtQ=Q@,/Q2h*3QQ=JhJ;J

Answer 14

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

Answer 15

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

Answer 16

Haskell 73 Bytes 73 Chars

r n |even n=n`quot`2
    |otherwise=3*n+1
c=length.takeWhile(/=1).iterate r

Answer 17

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

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

Answer 19

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  v`1:<
^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.

Answer 20

Haskell, 43 Bytes

c 1=0
c x|odd x=1+c(3*x+1)|1<2=1+c(x`div`2)

Usage: c 7-> 16

Answer 21

Python 2, 59 57 55 54 bytes

i=0;n=input()
while~-n:n=[n/2,n*3+1][n%2];i+=1
print i

Answer 22

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

Answer 23

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

Answer 24

Game Maker Language, 63 61 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.

Answer 25

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

Answer 26

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

With comments

# 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

Answer 27

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!

Answer 28

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.

Answer 29

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
🍉

Answer 30

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)