68
\$\begingroup\$

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

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
\$\endgroup\$

101 Answers 101

1
\$\begingroup\$

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)))))
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

C, 38 bytes

g(v){return v^1?1+g(v&1?v*3+1:v/2):0;}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 38 bytes

a(n)=if(n==1,0,a(if(n%2,3*n+1,n/2))+1)

Try it online!

Equivalent to this readable C code:

int b(n)
{
    if (n % 2)
        return 3 * n + 1;
    else
        return n / 2;
}

int a(n)
{
    if (n == 1)
        return 0;
    else
        return a(b(n)) + 1;
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Casio-Basic, 83 72 bytes

71 bytes for code, +1 for n as parameter.

0⇒z
While n≠1
piecewise(mod(n,2),3n+1,n/2)⇒n
z+1⇒z
WhileEnd
Print z
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

tinylisp repl, 68 bytes

(load library)(d f(q((n)(i(e n 1)0(inc(f(i(even? n)(/ n 2)(inc(* 3 n

Try it online! (Note that the repl auto-closes parentheses; on TIO, they have to be explicitly closed, which I've done in the footer.)

This is the same recursive solution as, e.g., Carcigenicate's Clojure answer. Because tinylisp has only addition and subtraction built in, I load the standard library to get even?, /, and * (and inc, which is the same length as a 1 but looks nicer). Other library functions would make the code longer; for instance, I'm defining the function manually with (q((n)(...))) rather than using (lambda(n)(...)). Here's how it would look ungolfed and indented:

(load library)
(def collatz
  (lambda (n)
    (if (equal? n 1)
      0
      (inc
        (collatz
          (if (even? n)
            (/ n 2)
            (inc (* 3 n))))))))

Going the other direction, here's a 101-byte solution that doesn't use the library. The E function returns n/2 if n is even and the empty list (falsey) if n is odd, so it can be used both to test evenness and to divide by 2.*

(d E(q((n _)(i(l n 2)(i n()_)(E(s n 2)(a _ 1
(d f(q((n)(i(e n 1)0(a 1(f(i(E n 0)(E n 0)(a(a(a n n)n)1

* Only works for strictly positive integers, but that's exactly what we're dealing with in this challenge.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

QBIC, 34 33 bytes

:{~-a|_Xb\b=b+1~a%2|a=a*3+1\a=a/2

Pretty straightforward:

:           Name the Command Line Parameter 'a'
{           Start an infinite loop
~-a|_Xb     If 'a' = 1 (or -a = -1, QB's TRUE value), quit printing 'b'
\           ELSE (a > 1)
b=b+1       Increment step counter
~a%2        In QBasic, 8 mod 2 yields 0, and 0 is considered false
|a=a*3+1    Collatz Odd branch
\a=a/2      Collatz Even branch
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Attache, 11 bytes

CollatzSize

Try it online!

Not much to say...

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Wumpus, 22 bytes

I]=2:~3*)=&~~!0~.
l(O@

Try it online!

Explanation

The first line is the main loop which iterates the Collatz function until we get 1. We keep track of the number of steps by growing the stack by one element on each iteration.

I   Read a decimal integer N from STDIN. At EOF (i.e. on subsequent 
    iterations) this pushes 0 instead.
]   Rotate the stack right. On the first iteration, this does nothing, but
    afterwards this moves the 0 to the bottom of the stack.
=   Duplicate N.
2:  Compute N/2.
~   Swap with the other copy of N.
3*) Compute 3N+1.
=   Duplicate.
&~  3N+1 times: swap N/2 and 3N+1. If N is odd, 3N+1 is even and vice versa.
    We end up with the value that we want on top and the incorrect one
    underneath.
~   Swap them once more.
!   Logical NOT. 3N+1 is always positive and N/2 gives 0 iff N = 1 (in which 
    case N/2 will also be on top of the stack). So this essentially gives us
    1 iff N = 1 (and 0 otherwise). Call this value y.
0~. Jump to (0, y), i.e. to the beginning of the second line once we reach N = 1
    and to the beginning of the first line otherwise.

Once we reach 1:

l   Push the stack depth. The stack holds one zero for each iteration as well
    as the final result. But note that we won't terminate until the iteration
    that process 1 itself (because we check the condition at the end of
    the loop, but based on its initial N). So the stack depth is one
    greater than the number of steps to reach 1.
(   Decrement.
O   Print as decimal integer.
@   Terminate the program.

I've got an alternative 22 byte solution, but unfortunately I haven't found anything shorter yet:

I]3*)=2%5*):=(!0~.
lO@
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Java (OpenJDK 8), 54 bytes

a->{int c=0;for(;a!=1;c++)a=a%2>0?a*3+1:a/2;return c;}

Try it online!

This answer is a little to simple to justify an explanation, it’s just a while loop and a ternary expression.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Octave, 65 bytes

@(x)eval 'k=0;do++k;if mod(x,2)x=3*x+1;else x/=2;end,until x<2,k'

Try it online!

It's time we have an Octave answer here. It's a straight forward implementation of the algorithm, but there are several small golfs.

Using do ... until instead of while ... end saves some bytes. Instead of having while x>1,k++;...end, we could have do++k;...until x<2, saving two bytes. Using eval in an anonymous function saves a few bytes, compared to having input(''). Also, skipping the parentheses in the eval call saves some bytes.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Ruby, 48 bytes

(f=->n{n>1&&1+f[n%2<1?n/2:3*n+1]||0})[gets.to_i]

Same as other Ruby, but using n%2?a:b syntax instead of [a,b][n%2]. Saves one char.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You mention that you save one byte off of the other Ruby answer yet your answer is 13 bytes longer because of (...)[gets.to_i]. Even if I remove that (which doesn't break your answer) you still have the same length as the other answer. This is ok, I just thought maybe you might have made a mistake. \$\endgroup\$ – Ad Hoc Garf Hunter Jun 19 '18 at 14:11
1
\$\begingroup\$

PHP, 80 73 Bytes

Tried a recursive function Try it here! (80 Bytes)

Try it online (73 Bytes)

Code (recursive function)

function f($n,$c=0){echo($n!=1)?(($n%2)?f($n*3+1,$c+1):f($n/2,$c+1)):$c;}

Output

16 -> 4
2 -> 1
5 -> 5
7 -> 16

Explanation

function f($n,$c=0){ //$c counts the iterations, $n the input
echo($n!=1)?    
(($n%2)?
    f($n*3+1,$c+1): //$n is odd
    f($n/2,$c+1))   //$n is even
:$c;                 //echo $c (counter) when n ==1
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ No, the test cases aren't part of the byte count. Your submission looks fine as it is. \$\endgroup\$ – Martin Ender Mar 26 '18 at 13:42
1
\$\begingroup\$

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
            ;   Discard TOS
             î  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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This is 12 bytes if you don't use the collatz operator \$\endgroup\$ – Jo King Oct 6 '18 at 8:39
  • \$\begingroup\$ 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 \$\endgroup\$ – maxb Oct 6 '18 at 9:25
  • \$\begingroup\$ @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. \$\endgroup\$ – maxb Nov 15 '18 at 8:15
  • \$\begingroup\$ Lol, my bad. In that case, it would be 14 bytes \$\endgroup\$ – Jo King Nov 15 '18 at 9:14
1
\$\begingroup\$

C (gcc), 43 33 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Pushy, 24 bytes

Zvt$h2C3*h}2/}2%zFhFt;F#

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

JavaScript, 35 bytes

f=(n,c)=>n<2?c:f(n%2?n*3+1:n/2,-~c)

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Japt, 18 15 bytes

É©Òß[U*3ÄUz]gUv

Try it

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Wren, 68 bytes

Fn.new{|n|
var c=0
while(n>1){
n=n%2==0?n/2:n*3+1
c=c+1
}
return c
}

Try it online!

Explanation

Fn.new{|n| // New anonymous function with param n
var c=0    // Declare a variable c as 0
while(n>1){ // While n is larger than 1:
n=n%2==0?          // If n is divisible by 2:
         n/2:      // Halve n
             n*3+1 // Otherwise, triple n & increment.
c=c+1              // Increment the counter
}                  // This is here due to Wrens bad brace-handling system
return c           // Return the value of the counter
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Keg -rR, 23 bytes (SBCS)

I really need to remember those new instructions.

0&{:1>|:2%[3*⑨|½]⑹

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Kotlin, 63 bytes

{var n=it
var c=0
while(n>1){n=if(n%2==0)n/2 else n*3+1
c++}
c}

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Abusing a built-in (F) saves 4 bytes - the other change is just a different way of doing the if, not golfier. \$\endgroup\$ – JayCe Jun 14 '18 at 19:35
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What's "Haskell 2"? \$\endgroup\$ – nyuszika7h Dec 6 '16 at 23:14
  • 2
    \$\begingroup\$ @nyuszika7h: a typo \$\endgroup\$ – nimi Dec 6 '16 at 23:14
0
\$\begingroup\$

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);}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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);
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

S.I.L.O.S, 76 bytes

readIO
lbla
I=1-(i%2)
if I x
i=i*6+2
lblx
i/2
x+1
I=1-i
I|
if I a
printInt x

Try it online!

Somewhat naively implements the spec. It avoids a couple extra lines at the cost of performance by multiplying i by 6 and adding 2, then dividing by two when the number is odd.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Emojicode, 139 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.