Collatz Conjecture

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.