collatz.md

I implemented simple (dumb) algorithm for finding the largest Collatz trajectory (see Collatz conjecture) for all numbers < 100,000,000 in Python, Rust and Elixir.

I benchmarked them with time command, assuming boot time is negligible (Python and Elixir need ~1 sec to boot before the calculation loop starts but their runtime is in hundreds of seconds anyway. Rust program boots in couple of milliseconds.)

Results:

Python (mem usage gradually grows up to ~1 GB):

174.02 real       173.34 user         0.60 sys

Rust (mem usage of 191 MB):

1.27 real         1.21 user         0.05 sys

Elixir (max mem usage 7.2 GB of RAM, but mostly between 3-4 GB):

305.90 real       275.36 user        35.41 sys

If we take Rust (shortest runtime) as baseline then:

lang	times slower	times memory
Rust	1	1
Python	137	5.2
Elixir	241	18.3 (mostly) / 37.6 (max)

Python impl

#!/usr/bin/env python3

# benchmarked with:
#   time python3 collatz.py

SIZE = 100000000 # 100M
# SIZE = 1000000

results = []
longest_number = 0
longest_steps = 0

for number in range(SIZE):
    n = number
    steps = 0

    while n > 1:
        if n < number:
            steps += results[n]
            break

        steps += 1

        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1

    results.append(steps)

    if steps > longest_steps:
        longest_steps = steps
        longest_number = number

print(f'{longest_number} - {longest_steps} steps')

Rust impl

// benchmarked with:
//   cargo build --release; time target/release/collatz

const SIZE: usize = 100_000_000;
// const SIZE: usize = 1_000_000_000;

fn main() {
    let mut results: Vec<u16> = vec![0; SIZE];
    let mut longest_number = 0;
    let mut longest_steps = 0;

    for number in 0..SIZE {
        let mut n = number;
        let mut steps = 0;

        while n > 1 {
            if n < number {
                steps += results[n];
                break;
            }

            steps += 1;

            if n % 2 == 0 {
                n = n / 2;
            } else {
                n = 3 * n + 1;
            }
        }

        results[number] = steps;

        if steps > longest_steps {
            longest_steps = steps;
            longest_number = number;
        }
    }

    println!("{} - {} steps", longest_number, longest_steps);
}

Elixir impl

# benchmarked with:
#   time elixir collatz.ex

defmodule Collatz do
  @size 100_000_000

  def run do
    run(0, %{}, 0, 0)
  end

  def run(number, results, longest_number, longest_steps) when number < @size do
    steps = count_steps(number, number, 0, results)
    results = Map.put(results, number, steps)

    if steps > longest_steps do
      run(number + 1, results, number, steps)
    else
      run(number + 1, results, longest_number, longest_steps)
    end
  end

  def run(_number, _results, longest_number, longest_steps) do
    IO.puts("#{longest_number} - #{longest_steps} steps")
  end

  defp count_steps(n, number, steps, results) when n > 1 do
    if n < number do
      steps + results[n]
    else
      n =
        if rem(n, 2) == 0 do
          div(n, 2)
        else
          3 * n + 1
        end

      count_steps(n, number, steps + 1, results)
    end
  end

  defp count_steps(_n, _number, steps, _results), do: steps
end

Collatz.run()