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

137 Answers 137

2
\$\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!

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

Pushy, 24 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ wait. why does halve not work? floating point errors, i guess? \$\endgroup\$
    – ASCII-only
    Jan 19, 2019 at 1:19
  • \$\begingroup\$ yup, it turns integers into floats and I dont see a way to implicitly turn it into an integer again after halving \$\endgroup\$
    – Wisław
    Jan 19, 2019 at 1:30
  • \$\begingroup\$ 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.) \$\endgroup\$ Jan 28, 2019 at 14:32
  • \$\begingroup\$ Thanks @KevinCruijssen! I am still bad at taking advantage of implicit input :-) \$\endgroup\$
    – Wisław
    Jan 28, 2019 at 15:00
  • 1
    \$\begingroup\$ 14 bytes \$\endgroup\$
    – Zylviij
    Apr 30, 2019 at 19:10
2
\$\begingroup\$

Aceto, 33 bytes

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

Explanation:

Read an integer:

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

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.

\$\endgroup\$
2
\$\begingroup\$

Racket, 51 characters, 28 brackets

(define(a n)(do([i 0(+ i 1)][x n(if(even? x)(/ x 2)(+ 1(* 3 x)))])((= 1 x) i)))

Praise the do. Love the do.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf! Nice first answer. \$\endgroup\$ Dec 13, 2021 at 23:33
2
\$\begingroup\$

Julia 1.0, 29 bytes

!n=n>1&&1+![n÷2,3n+1][n%2+1]

Try it online!

Based on Dennis' answer

\$\endgroup\$
2
\$\begingroup\$

LOLCODE, 217 bytes

HAI 1
I HAS A N
GIMMEH N
I HAS A C
IM IN YR L UPPIN YR D WILE DIFFRINT N 1
BOTH SAEM MOD OF N 2 0,O RLY?
YA RLY,N R QUOSHUNT OF N 2
NO WAI,N R SUM OF PRODUKT OF N 3 1
OIC
C R D
IM OUTTA YR L
VISIBLE SUM OF C 1
KTHXBYE

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Alice, 26 bytes

/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.
\$\endgroup\$
0
2
\$\begingroup\$

Pip, 23 21 19 bytes

a>1&URE[HVa3*a+1]@a

Try It Online! Note that this is a recursive solution; moderately large numbers of iterations will cause a recursion error.

Explanation

a>1&URE[HVa3*a+1]@a
a>1                  Is the argument greater than 1?
   &                 If not, return 0; if so, return
    U                1 plus
     RE              Recursive call to the main function with this argument:
       [        ]      Construct a list containing two elements:
        HVa              Half of the argument
           3*a+1         3 times the argument plus 1
                 @     Select the element at (modular) index of
                  a    The argument

A non-recursive solution in 21 bytes:

Wa>1&Uia:%a?3*a+1HVai
                       i is 0; a is first command-line argument (implicit)
Wa>1                   While a>1
    &Ui                (and if it is, increment i):
       a:               Set a to:
         %a?             If a mod 2 is nonzero (a is odd),
            3*a+1         3*a+1;
                 HVa      else, halve a
                    i  Autoprint i, the iteration count

The original 23-byte solution in Pip Classic is similar: Try it online!

\$\endgroup\$
2
\$\begingroup\$

Husk, 12 11 bytes

€2¡?o→*3½%2

Try it online!

Explanation

€2¡?o→*3½%2
  ¡          Infinitely iterate the following function:
   ?           If
         %2    the argument mod 2 is 1:
    o            Compose:
     →             Increment
      *3           Times three
        ½      Else, halve
€2           Index (1-based) of first occurrence of 2 in that infinite list
\$\endgroup\$
1
\$\begingroup\$

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.

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

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.

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

Pyth 27 23 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

\$\endgroup\$
5
  • \$\begingroup\$ Btw. W>Q1 is the same thing as WtQ \$\endgroup\$
    – Jakube
    May 29, 2015 at 9:05
  • \$\begingroup\$ I didn't even look at the date ;) And thanks. \$\endgroup\$
    – gcq
    May 29, 2015 at 9:06
  • \$\begingroup\$ 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. \$\endgroup\$
    – Jakube
    May 29, 2015 at 9:07
  • \$\begingroup\$ The usage of f...1 not really documented (at least not good). It basically means: "find the first number >= 1, that satisfies ..." \$\endgroup\$
    – Jakube
    May 29, 2015 at 9:12
  • \$\begingroup\$ That's good to know, tried to find that on the docs but no luck \$\endgroup\$
    – gcq
    May 30, 2015 at 20:03
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\$ Apr 18, 2016 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\$ Apr 18, 2016 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\$ Apr 18, 2016 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\$

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, 2018 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\$ Mar 26, 2018 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\$

JavaScript, 35 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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