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
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Challenges

Collatz conjecture; Count the tries to reach $1$

+7
−0

Background

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

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. Thanks to @Shaggy for the link!

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

15 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

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

+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 39 bytes

f 1=0
f n=1+f([div n 2,n*3+1]!!mod 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

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

+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

Lua 5.4, 67 60 bytes

function(x)return x==1 and 0 or 1+f(({x/2,3*x+1})[x%2+1])end

Attempt This Online!

Credits to @Moshi for more shortening.

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

1 comment thread

60 bytes (2 comments)
+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

+1
−0

C (gcc), 43 38 bytes

f(i){return i>1?f(i%2?3*i+1:i/2)+1:0;}

Attempt This Online!

Credits to @Moshi for shortening the code.

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

1 comment thread

38 (1 comment)
+1
−0

shortC, 47 bytes

a,b;AOK"%d",&b);b-1;b=b%2?b*3+1:b/2)a++;R"%d",a

Try it online!

From @ugoren's C answer from CGCC.

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

0 comment threads

+1
−0

Wolfram Language (Mathematica), 38 bytes

Tr[1^ResourceFunction["Collatz"]@#]-1&

Don't Try it online!

Doesn't work on TIO due to using the Collatz builtin which needs to be downloaded from the Function Repository

Relatively badly-golfed version without ResourceFunction (52 bytes):

i=0;If[#!=1,i++;#0[If[EvenQ@#,Floor[#/2],3 #+1]],i]&

Try it online!

Had to add a slightly janky print statement into the main body for the value of i to get reset on each evaluation.

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

1 comment thread

Saving 9 characters in the version without Collatz builtin (1 comment)
+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

AWK, 46 bytes

{c=0;for(n=$0;n-1;c++)n=n%2?n*3+1:n/2;print c}

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

Java (JDK), 150 bytes

interface M{static void main(String[]a){int i=new java.util.Scanner(System.in).nextInt(),j=0;for(;i!=1;j++){i=i%2==1?i*3+1:i/2;}System.out.print(j);}}

Try it online!

From my shortC answer.

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

0 comment threads

+0
−0

J, 35 char

<:#-:`(>:@:*&3)@.(2&|)^:(1&<)^:(<_)

How it works:

NB. <: subtract one from number result on right

NB. # count number of items from list result on right

NB. -: if intermediate result is even, half the value

NB. ` make a gerund from verb to left and verb to right

NB. (>:@:*&3) if intermediate result is odd, multiply by 3

NB. @. choose from gerund using index on right

NB. (2&|) mod 2 used as index into gerund on left

NB. ^:(1&<) repeat verb on left while intermediate value is >1

NB. ^:(<_) repeat verb on left until intermediate value stops changing and keep intermediate values in a list

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!

Like what we're doing? Support us! Donate