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.