Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs

Dashboard
Notifications
Mark all as read
Challenges

Collatz conjecture; Count the tries to reach $1$

+5
−0

Background

Check out this video on the Collatz conjecture, also known as A006577[1].

If you don't know what this is, we're given an equation of $3x + 1$, and it is applied this way:

  • If $x$ is odd, then $3x + 1$.
  • If $x$ is even, then $\frac{x}{2}$.

This will send us in a loop of 4 → 2 → 1 → 4 → 2 → 1..., which got me into making this challenge.

Challenge

Write a program that establishes the Collatz conjecture:

  • Take input of a positive integer. This will be the $x$ of the problem.
  • Read the background for how it works, or watch the video for further explanation.
  • The result should be how many turns it would take before reaching $1$. There, the sequence stops.
  • This is code-golf, so the shortest program in each language wins!

Test Cases

From 1 to 10:

1  → 0  (1)
2  → 1  (2 → 1)
3  → 7  (3 → 10 → 5 → 16 → 8 → 4 → 2 → 1)
4  → 2  (4 → 2 → 1)
5  → 5  (5 → 16 → 8 → 4 → 2 → 1)
6  → 8  (6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1)
7  → 16 (7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1)
8  → 3  (8 → 4 → 2 → 1)
9  → 19 (9 → 28 → 14 → 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1)
10 → 6  (10 → 5 → 16 → 8 → 4 → 2 → 1)

More of these can be found on OEIS (see reference 1). Thanks to @Shaggy for the link!


  1. https://oeis.org/A006577 ↩︎

Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

0 comment threads

9 answers

+4
−0

JavaScript, 28 bytes

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

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+3
−0

Python 3, 48 42 39 bytes

Saved 6 bytes thanks to Hakerh400‭ in the comments

Saved another 3 bytes thanks to user in the comments

f=lambda n:n-1and-~f([n//2,3*n+1][n%2])

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

2 comment threads

39 bytes using ~- from Shaggy's answer and [] (2 comments)
42 bytes (1 comment)
+3
−0

Haskell, 43 bytes

f n|n<2=0|odd n=1+f(n*3+1)|0<1=1+f(div n 2)

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+2
−0

Sclipting, (UTF-16) 44 34 32 bytes

貶要❶갠剩❷隔❸增갰乘嗎終并長貶

Because comparing with 1 is expensive (requires copying and decrementing), we instead use a modified version of the Collatz sequence - namely, we use the sequence where every number is one lower. This allows us to compare with 0 instead.

Input of n
貶       Decrement n
要       While n (is non-zero)
  ❶갠剩    Take n mod 2
  ❷隔      Compute n integer divided by 2 (1)
  ❸增갰乘  Compute n plus 1 and multiplied by 3 (2)
  嗎       Condition on n mod 2; if odd, take (1) else take (2)
終       End while
并長貶   Join stack into a list, take the length and decrement by one
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+2
−0

Japt, 15 bytes

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

Try it

É©Òß[U*3ÄUz]gUv     :Implicit input of integer U
É                   :Subtract 1
 ©                  :Logical AND with
  Ò                 :Negate the bitwise NOT of (i.e., increment)
   ß                :Recursive call with input
    [               :  Array containing
     U*3Ä           :    U*3+1
         Uz         :    U floor divided by 2
           ]        :  End array
            g       :  Get element at 0-based index
             Uv     :    Is U divisible by 2?
Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+2
−0

BQN, 31 28 bytes

{1+(1≠𝕩)◶¯1‿𝕊2(|⊑÷˜∾1+3×⊢)𝕩}

Try it online!

An anonymous function which takes a number.

the ¯1 branch is a bit tacky but saves a byte over (1+𝕊).

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+1
−0

Scala, 50 bytes

Stream.iterate(_)(x=>Seq(x/2,3*x+1)(x%2))indexOf 1

Try it in Scastie!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+1
−0

Ruby, 33 bytes

Recursive lambda solution.

c=->n{n<2?0:1+c[n%2<1?n/2:n*3+1]}

c=->n{                          }  # c = lambda taking `n`
      n<2? :                       # if n < 2...
          0                        # return 0...
            1+c[               ]   # else return 1 + collatz count for...
                n%2<1?   :         # if n is even... 
                      n/2          # n / 2...
                          n*3+1    # else 3n + 1

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

+0
−0

Lua, 88 bytes

function f(x)i=0while x~=1 do if x%2==1then x=x*3+1 else x=x/2 end i=i+1 end print(i)end

Try it online!

Just learned you can do var_name = function(args) end, but it doesn't change the byte count, so I won't use it.

Why does this post require moderator attention?
You might want to add some details to your flag.

0 comment threads

Sign up to answer this question »

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!