Project Euler Problem 5

Hi guys, im resolving problem 5, and reach this solutions :

@numeros Enum.to_list(2..20)

  def valor do
    Stream.iterate(21,&(&1 + 1))
    |> Stream.filter(&valores(&1, @numeros) == true)
    |> Enum.take(1)

  def valores(_num,[]) do

  def valores(num, [cabeza | cola]) do
    case rem(num, cabeza) do
      0 -> valores(num,cola)
      _ -> false

And it take like 38 seconds to conclude.

Then i looked for other solutions and find this:

@numbers Enum.to_list 20..2

  def solve do
    _solve(21, @numbers)

  defp _solve(n, []), do: n

  defp _solve(n, [h | t]) do
    case rem(n, h) do
      0 -> _solve(n, t)          
      _ -> _solve(n+1, @numbers) 

And reach the result in 5 seconds. Im wonder why in one take so much time and the other is more faster?

1 Like

The second solution uses a kind of Tail Call Optimization. In general, if you can make the last expression in a recursive function a call to that function, the compiler can optimize that kind of recursion.

The second solution is faster because both branches of the case are TCO. While not strictly TCO, the compiler is smart enough to do the right thing in this case.

While in many languages TCO is absolutely required for large recursions to work at all the situation in Elixir and Erlang is quite different. This blog post is an interesting read.

In the case of the Euler problems, (at least the early ones), the size and type of the recursions is so large that TCO solutions will almost always be faster. But those problems are somewhat of a special edge case. The important lesson to take away is that benchmarking on typical inputs is the only way to know for sure whether changing your code is faster.