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

138 Answers 138

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

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.

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

Lua, 75 bytes

function C(x)z=0 while x>1 do x=({x//2,3*x+1})[x%2+1]z=z+1 end return z end

Try it online!

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

Python - 101 bytes

n=int(input())
m=0
while n>1:
  if n%2==0:
    n=n/2
    m+=1
  else:
    n=3*n+1
    m+=1
if n==1:
  print(m)

This assumes n is inputted to STDIN as an integer. If it is not explicitly that, a type check is most certainly possible, but would cost a few bytes, i.e.

if type(n) != int: 
 print(N/A)

(edit 1: input is so expensive)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 71 bytes \$\endgroup\$
    – oeuf
    Apr 10, 2022 at 3:55
1
\$\begingroup\$

Burlesque, 26 bytes

1{J2dv{2./}{3.*+.}IE}C~1Fi

Try it online!

1          #Needed for C~
{
 J         #Duplicate
 2dv       #Even
 {2./}     #Halve
 {3.*+.}   #3n+1
 IE        #If even, else
}
C~         #Continue indefinitely
1Fi        #Find index of 1
\$\endgroup\$
1
\$\begingroup\$

Python 3, 64 bytes

def f(n,a=0):
    while n>0:n=[n//2,n*3+1][n%2];a+=1
    yield a

Try it online!

\$\endgroup\$
1
\$\begingroup\$
INPUT A
Y:
IF A MOD 2=0 THEN
  B=A/2
  PRINT B
  A=B
  ELSE
  B=A*3+1
  PRINT B
  A=B
  END IF
IF A>1 THEN
  GOTO Y
  ELSE
  END IF
\$\endgroup\$
1
  • 6
    \$\begingroup\$ Welcome to Code Golf! Could you edit in the language used, along with the length (in bytes) of your code, as this is a [code-golf] challenge? I've edited your answer slightly to format the code properly \$\endgroup\$ Jan 23, 2022 at 20:31
1
\$\begingroup\$

tinylisp, 68 67 bytes

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

Try it online!

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 odd?, /, *, and inc. 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 (odd? n)
            (add2 (* 3 n) 1)
            (/ n 2)))))))

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

Desmos, 63 bytes

i->.5si(5k+1)+sk-s+1,o->o+s
i=\ans_0
o=0
k=mod(i,2)
s=sign(i-1)

Output is the value of o after the code finishes running.

Have fun trying to figure out how this works! (It's really not as complicated as it seems)

Try It On Desmos!

Try It On Desmos! - Prettified

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

Ruby, 60 bytes

n,i=gets.to_i,0;while n>1 do n=n%2==0?n/2:n*3+1;i+=1 end;p i

Pretty readable and easy to understand compared to the previous Ruby submission.

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ 56 bytes \$\endgroup\$
    – naffetS
    Apr 10, 2022 at 20:17
1
\$\begingroup\$

C (gcc) 38, 37 bytes (thanks to @UnrelatedString)

c(x){return~-x?-~c(x%2?3*x+1:x/2):0;}

First recursive solution that came to mind. Fairly simple. Explanation (ungolfed):

int c() {
 return~-x? //If x!=1 
       -~c(x%2?3*x+1:x/2) // Compute the next term and recurse on that term. Add 1.  
       : 
       0; //Base case
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ -1 \$\endgroup\$ Apr 8, 2022 at 6:46
  • 1
    \$\begingroup\$ Nice! Thanks. I forgot to take advantage of two's complement! \$\endgroup\$
    – Qaziquza
    Apr 8, 2022 at 8:02
1
\$\begingroup\$

Factor + project-euler.014, 22 bytes

[ collatz length 1 - ]

Try it online!

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

Haskell (54 bytes)

c n a|n<2=a|odd n=c(3*n+1)(a+1)|even n=c(div n 2)(a+1)

This function takes two arguments, the value n and an accumulator a. The type signature is: c :: Int -> Int -> Int.

In expanded form:

collatz n acc
  | n < 2  = acc
  | odd n  = collatz (3 * n + 1) (acc + 1)
  | even n = collatz (div n 2) (acc + 1)
\$\endgroup\$
1
1
\$\begingroup\$

brev, 71 bytes

(rec(f x)(cond((= x 1)0)((odd? x)(+(f(+(* 3 x)1))1))(1(+(f(/ x 2))1))))
\$\endgroup\$
1
\$\begingroup\$

Fig, \$15\log_{256}(96)\approx\$ 12.347 bytes

#?{x}oX?Ox}*3xH

Try it online!

This challenge does not lend itself well to Fig's implicit inputs...

#?{x}oX?Ox}*3xH
  {x            # Decrement the input
#?              # If ^ is false, return ^, else return...
     oX         # Call this function with the following argument:
       ?Ox      # If odd
           *3x  # Multiply by 3
          }     # Add 1
                # Else
              H # Halve
    }           # After calling this function, increment the result
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 17 12 11 bytes

∷[T›|½)İ2ḟ⇧

Try it Online!

-5 bytes thanks to lyxal

Removed flag thanks to emanresu A.

\$\endgroup\$
4
  • \$\begingroup\$ Try it Online! for 12 bytes \$\endgroup\$
    – lyxal
    Apr 10, 2022 at 3:04
  • \$\begingroup\$ Flagless 11 (husk port) \$\endgroup\$
    – emanresu A
    Jan 30, 2023 at 7:00
  • \$\begingroup\$ @emanresuA Alternative: ‡₍½‡T›iİ2ḟ⇧ \$\endgroup\$
    – naffetS
    Jan 30, 2023 at 18:20
  • \$\begingroup\$ Try it Online! for 10 bytes/7.875 bytes. Uses newer functionality that didn't exist back when this answer was made. \$\endgroup\$
    – lyxal
    Jul 18, 2023 at 13:28
1
\$\begingroup\$

Thunno 2, 17 bytes

(1Q;Dɗ?3×⁺:½;ẋ)x⁻

Attempt This Online!

Only works in Thunno \$\le 2.1.9\$. In versions \$\ge 2.1.10\$, can be replaced with ẋ⁺.

Explanation

(1Q;Dɗ?3×⁺:½;ẋ)x⁻  # implicit input; x is initialised to 1
(1Q;          )    # while TOS != 1:
    D              #   duplicate
     ɗ?            #   if TOS is odd:
       3×⁺         #     triple and increment
          :        #   else:
           ½       #     halve
            ;ẋ     #   increment x
               x⁻  # push x and decrement
                   # implicit output
\$\endgroup\$
1
\$\begingroup\$

Nekomata, 10 bytes

ˡ{1>ᵉ½3*→I

Attempt This Online!

ˡ{1>ᵉ½3*→I
ˡ{          Repeat the following function until it fails, and count the number of steps:
  1>            Check if greater than 1
    ᵉ           Parallelly apply the following two functions:
     ½              Check if it is even, and divide by 2
      3*→           Multiply by 3 and add 1
         I      Choose the first result that does not fail
\$\endgroup\$
1
\$\begingroup\$

Uiua, 23 bytes

⧻⍢(⊂0⟨÷2|+1×3⟩◿2.|¬∊2)¤

Explain:

⧻                       # length of list
 ⍢(              |   )  # do while
   ⊂0                   # prepend 0 to the list
     ⟨÷2|+1×3⟩◿2.       # apply collatz the the whole list
                  ¬∊2   # while the list doesn't contain 2
                      ¤ # arg as list
\$\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
\$\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, 2018 at 19:35
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);}
\$\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!

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

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