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
Community Proposals
Community Proposals
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!

History
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!

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

0 comment threads

+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!

History
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
History
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!

History
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)
+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+𝕊).

History
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?
History
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.

History
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!

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

0 comment threads

+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.

History
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!

History
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!

History
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.

History
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

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.

History
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

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

History
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.

History
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 »