# Type-level Collatz Sequence

The *Collatz conjecture* is an unsolved problem in mathematics. It states that for any positive integer `n`

, the sequence of numbers generated by the following algorithm will eventually reach `1`

. These are also called the *hailstone numbers*.

```
function collatz(n: number): number {
return n % 2 === 0 ? n / 2 : 3 * n + 1;
}
```

The sequence generated by a given $n$ is the sequence of numbers `n`

, `collatz(n)`

, `collatz(collatz(n))`

, `collatz(collatz(collatz(n)))`

, and so on. This is known as the *Collatz sequence* of $n$, and ends when ‘1’ is reached.

## Typescript

This sequence serves as an entertaining challenge for performing type-level arithmetic, including addition, multiplication, and conditional logic.

Additionally, since even small numbers may generate large sequences, this serves as a benchmark for the performance and depth-limit of type-level computations.

## Method

The method I used was to compose various type-level operations into a single type-level function, which I called `Collatz`

. This function takes a type `N`

and returns the next element in the Collatz sequence of `N`

.

```
import { $, Kind, Conditional, Function, NaturalNumber } from "hkt-toolbelt";
export type Collatz = Conditional.If<
NaturalNumber.IsEven,
$<NaturalNumber.DivideBy, 2>,
Kind.Pipe<[$<NaturalNumber.Multiply, 3>, NaturalNumber.Increment]>
>;
```

These modules come from my library hkt-toolbelt. Essentially, these higher-order types compose to form a point-free programming language. All modules are highly optimized for performance and type inference.

For generating the `CollatzSequence`

, I used a fixed point combinator variant that I call `FixSequence`

, which takes a homomorphic higher-order type $F$ and an initial value $n$ and returns the sequence $[n, F(n), F^2(n), F^3(n), …]$ until the sequence reaches a fixed point (if it ever does).

```
import { $, Kind, Combinator, Conditional, Function, NaturalNumber } from "..";
export type CollatzSequence = $<
Combinator.FixSequence,
Conditional.If<Conditional.Equals<1>, Function.Constant<1>, Collatz>
>;
```

## Results

The screenshot below shows type inference for the Collatz sequence of $n = 871$, which has a sequence length of 179.

The implementation even supports initial values into the millions:

```
import { $, NaturalNumberTheory } from "hkt-toolbelt";
type R = $<NaturalNumberTheory.CollatzSequence, 3_732_423>["length"]; // 597
```

## Access

The `Collatz`

and `CollatzSequence`

utilities are available in the `NaturalNumberTheory`

module of hkt-toolbelt.