71
\$\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\$
0

109 Answers 109

1
\$\begingroup\$

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

Mathcad, 36 "bytes"

enter image description here

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.

\$\endgroup\$
3
  • \$\begingroup\$ Keyboard operations required to enter an expression please? \$\endgroup\$ – CalculatorFeline Apr 18 '16 at 17:00
  • \$\begingroup\$ 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. \$\endgroup\$ – Stuart Bruff Apr 18 '16 at 17:53
  • \$\begingroup\$ Answer Part 2: Download Mathcad Express (ptc.com/engineering-math-software/mathcad/free-download - cutdown version of Mathcad Prime 3.1) and then Mathcad 15 (ptc.com/engineering-math-software/mathcad/free-trial). This will allow you to play with them (M15 for 30 days, at least); Mathcad Express will give you full Prime 3.1 functionality for 30 days (including programming and symbolics). \$\endgroup\$ – Stuart Bruff Apr 18 '16 at 17:57
1
\$\begingroup\$

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.

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

C, 38 bytes

g(v){return v^1?1+g(v&1?v*3+1:v/2):0;}
\$\endgroup\$
0
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;
}
\$\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
\$\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.

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

Attache, 11 bytes

CollatzSize

Try it online!

Not much to say...

\$\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@
\$\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.

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

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

\$\endgroup\$
1
  • \$\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\$ – Wheat Wizard 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
}
\$\endgroup\$
1
  • \$\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\$

Python 2, 48 bytes

f=lambda n,s=0:s*(n<2)or f((n/2,3*n+1)[n%2],s+1)

Try it online!

Aaah, recursion.

# s*0 or s*1.
s*(n<2)

# while n>1, this will evaluate to 0 or f(n,s+1).
# Since positive integers are Truthy, this will return f().
# when n<2, this will return s without evaluating f().
s*(n<2)or f(...)
\$\endgroup\$
1
\$\begingroup\$

C (gcc), 43 33 bytes

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

Try it online!

\$\endgroup\$
0
1
\$\begingroup\$

Pushy, 24 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript, 35 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Japt, 18 15 bytes

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

Try it

\$\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
}
\$\endgroup\$
1
\$\begingroup\$

Keg -rR, 23 bytes (SBCS)

I really need to remember those new instructions.

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

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

MAWP, 36 bytes

@[!!2P2WA{%3W1M}<%2P>1A{1M}/1M\]%1A:

Works as per the basic rules. Increments existing 1 in stack for each step.

Prints out n-1.

Try it!

\$\endgroup\$
1
\$\begingroup\$

Pip, 23 bytes

Wa>1&++ia:a%2?3*a+1a/2i

Try it online!

Explanation

Wa>1&++ia:a%2?3*a+1a/2i
                         i is 0; a is first command-line argument (implicit)
Wa>1                     While a>1
    &++i                 (and if it is, increment i):
        a:                Set a to:
          a%2?             If a mod 2 is nonzero (a is odd),
              3*a+1         3*a+1;
                   a/2      else, a/2
                      i  Autoprint i, the iteration count
\$\endgroup\$
1
\$\begingroup\$

x86 machine code - 16 bytes

I'm just adapting from someone code, so this is example :

     6                                  .loop:
     7 00000000 0FBCC8                      bsf ecx, eax
     8 00000003 D3E8                        shr eax, cl
     9 00000005 83F801                      cmp eax, 1
    10 00000008 7406                        je .exit_loop
    11 0000000A 8D444001                    lea eax, [eax + 2*eax + 1]
    12 0000000E EBF0                        jmp .loop
    13                                  .exit_loop:
\$\endgroup\$
1
\$\begingroup\$

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 + 4 = 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, activating 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.

\$\endgroup\$
1
\$\begingroup\$

Rust, 62 bytes

fn c(x:u8)->u8{if x==1{0}else{c(if x%2==0{x/2}else{x*3+1})+1}}

This recursively determines the total. For 2 extra bytes u8 can be changed to u64 to support all 64-bit integers instead of just 8-bit ones.

New contributor
Smitop is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
1
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
\$\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.

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

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.