My program eats up the memory and the OS kills it

I’m new to Elixir (started yesterday) and as a first little program, I wanted to solve the Münchausen numbers problem.

“A Münchausen number is a number equal to the sum of its digits raised to each digit’s power. For instance, 3435 is a Münchausen number because 3^3+4^4+3^3+5^5 = 3435. The largest Münchausen number is less than 440 million.”

The problem is that my program eats up all my RAM (16 GB) and the OS kills the process. And I don’t understand what goes on with the garbage collector.

Here is my solution:

#!/usr/bin/env elixir

defmodule Munchausen do
  @cache [0] ++ for n <- 1..9, do: n ** n

  def get_cache(), do: @cache

  def explode(n), do: explode(n, [])

  # int, acc -> list[int]
  def explode(n, acc) when n == 0, do: acc

  def explode(n, acc) do
    digit = rem(n, 10)
    explode(div(n, 10), [digit | acc])
  end

  # int -> bool
  def is_munchausen(n) do
    digits = explode(n)
    li = for x <- digits, do: Enum.at(@cache, x)
    n == Enum.sum(li)
  end
end

defmodule Main do
  # @max 10_000
  @max 440_000_000

  def main() do
    # Munchausen.get_cache() |> IO.inspect
    for n <- 0..@max do
      # :erlang.garbage_collect()
      if rem(n, 1_000_000) == 0 do
        IO.puts("# #{n}")
      end
      if Munchausen.is_munchausen(n) do
        IO.puts(n)
      end
    end
  end
end

Main.main()

I know that it’s not optimal and slow. I’ll work on it.

Now the question is: why does it consume all my memory and how to prevent that? Thanks.

1 Like

A for loop like this will return a list containing the results of every evaluation of the do block:

for n <- 0..10 do
  IO.puts(n)
end

Running this in iex produces:

iex(1)> for n <- 0..10 do
...(1)>   IO.puts(n)
...(1)> end
0
1
2
3
4
5
6
7
8
9
10
[:ok, :ok, :ok, :ok, :ok, :ok, :ok, :ok, :ok, :ok, :ok]

Your Main.main function is building up a 440 million element list of :ok and nil, which it then discards when it exits.

3 Likes

Thanks. Right, the same thing happens in Python too:

$ python3
Python 3.10.4 (main, Mar 23 2022, 23:05:40) [GCC 11.2.0] on linux
>>> a = list(range(0, 440_000_000))
[1]    216403 killed     python3

So what’s the solution? How to iterate over the numbers from 0 until 440 million?

Update: I found the answer to my question:

Enum.each(0..@max, fn n ->
  if rem(n, 1_000_000) == 0 do
    IO.puts("# #{n}")
  end
  if Munchausen.is_munchausen(n) do
    IO.puts(n)
  end
end)
2 Likes

You might use stream to process the list lazily…

https://hexdocs.pm/elixir/1.13/Stream.html

2 Likes

Also, check out Memoize — memoize v1.4.0 , it makes the caching step trivial. For fibonnaci example:

defmodule Fib do
  use Memoize
  defmemo fibs(0), do: 0
  defmemo fibs(1), do: 1
  defmemo fibs(n), do: fibs(n - 1) + fibs(n - 2)
end
3 Likes