The Collatz conjecture is an unsolved problem in number theory where a sequence is constructed from iteratively applying \(f(n)\), such that,

\[f(n) = \begin{cases} \frac{n}{2} & \text{if } n \equiv 0 \pmod{2} \\ 3n + 1 & \text{if }n \equiv 1 \pmod{2}\,. \end{cases}\]The *conjecture* poses the question, that regardless of the starting integer, \(n\), the sequence will always conclude with \(1\).

```
using DataStructures
function collatz(n)
n == 1 && return nothing
isodd(n) ? 3n+1 : div(n, 2)
end
function collatzchain(k)
chain = Int[]
while !isnothing(k)
push!(chain, k)
k = collatz(k)
end
return chain
end
chaindict = OrderedDict{Int, Vector{Int}}()
@time @async for k in 1:100_000
chaindict[k] = collatzchain(k)
end
chaindict
> 0.000037 seconds (32 allocations: 2.188 KiB)
>
> OrderedDict{Int64, Vector{Int64}} with 100000 entries:
> 1 => [1]
> 2 => [2, 1]
> 3 => [3, 10, 5, 16, 8, 4, 2, 1]
> 4 => [4, 2, 1]
> 5 => [5, 16, 8, 4, 2, 1]
> 6 => [6, 3, 10, 5, 16, 8, 4, 2, 1]
> 7 => [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 8 => [8, 4, 2, 1]
> 9 => [9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, …
> 10 => [10, 5, 16, 8, 4, 2, 1]
> 11 => [11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 12 => [12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
> 13 => [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 14 => [14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 15 => [15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 16 => [16, 8, 4, 2, 1]
> 17 => [17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 18 => [18, 9, 28, 14, 7, 22, 11, 34, 17, 52 … 13, 40, 20, 10, 5, 16, 8, 4, …
> 19 => [19, 58, 29, 88, 44, 22, 11, 34, 17, 52 … 13, 40, 20, 10, 5, 16, 8, 4…
> 20 => [20, 10, 5, 16, 8, 4, 2, 1]
> 21 => [21, 64, 32, 16, 8, 4, 2, 1]
> 22 => [22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 23 => [23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
> 24 => [24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1]
> 25 => [25, 76, 38, 19, 58, 29, 88, 44, 22, 11 … 13, 40, 20, 10, 5, 16, 8, 4…
> ⋮ => ⋮
```

It appears that the sequence will always conclude with \(4, 2, 1\), but a definitive proof continues to elude mathematicians.

Since it appears that every sequence likely *will* conclude with the numbers \(4, 2, 1\), I'll modify the code to focus on checking the last three elements of each *collatz chain*.

```
@time @async for k in 1:10_000_000
if collatzchain(k)[end] != 1
println(k)
end
end
> 0.000039 seconds (34 allocations: 2.325 KiB)
>
> Task (done) @0x00000001b4cc5660
```

Well, at least the first ten million collatz chains all conclude with \(1\). We'll have to adjust the code if we want to check more than \(10^6\) chains since too many threads can be counter-productive and we definitely want to leverage parallelism for this task.

© Daniel Marvin. Last modified: July 19, 2021.