# Collatz conjecture; Count the tries to reach $1$

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

JavaScript, 28 bytes …

1y ago

[Sclipting], (UTF-16) 44 34 32 …

1y ago

[Python 3], 48 42 39 bytes …

1y ago

[Haskell], 43 39 bytes …

1y ago

Lua 5.4, 67 60 bytes ``` lu …

1y ago

[BQN], 31 28 bytes {1+( …

1y ago

Japt, 15 bytes É©Òß[U3Ä …

1y ago

[Wolfram Language (Mathematica …

1y ago

C (gcc), 43 38 bytes ``` C …

1y ago

[AWK], 46 bytes {c=0;fo …

1y ago

[shortC], 47 bytes a,b; …

1y ago

[Ruby], 33 bytes Recursive la …

1y ago

Scala, 50 bytes ```scala Str …

1y ago

J, 35 char ``` :@:&3)@.(2& …

1y ago

[Java (JDK)], 150 bytes …

1y ago

## 15 answers

# JavaScript, 28 bytes

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

#### 0 comment threads

#
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
```

#### 0 comment threads

#
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])
```

#
BQN, ~~31~~ 28 bytes

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

An anonymous function which takes a number.

the `¯1`

branch is a bit tacky but saves a byte over `(1+𝕊)`

.

#### 0 comment threads

# Japt, 15 bytes

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

```
É©Òß[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?
```

#### 0 comment threads

# 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
```

#### 0 comment threads

# 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]&
```

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

# Scala, 50 bytes

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

#### 0 comment threads

# 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);}}
```

#### 0 comment threads

# 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

## 0 comment threads