Project EulerのSmallest multipleをElixirで解く

[本当のプログラミング初心者にElixirを教えたことで得た学び - Line 1: Error: Invalid Blog('by Esehara' )](http://bugrammer.hateblo.jp/entry/2016/11/06/090000)を読んで、いくつかの問題を自分も試しにやってみたのでその成果を残しておきます。

## Smallest multiple

上の記事では「[Project Euler](https://projecteuler.net/)」というサイトにある問題をElixirで解いていくことについて触れられています。自分の場合、特に「[Smallest multiple](https://projecteuler.net/problem=5)」という問題が印象に残りました。

> 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

> What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

1から10までの自然数の最小公倍数は2520になるそうですが、1から20だとどうか？という問題です。

## 考え方

まずは問題を解くための考え方ですが、自分は以下のYahoo!知恵袋の解答が参考になりました。

[1～10までの自然数の最小公倍数が2520となるようですが、どのようにし... - Yahoo!知恵袋](http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1466216414)

ベストアンサーの解答はすでに2520という数字が分かっていたとき、なぜ1から10までの自然数の最小公倍数になるかを説明しているように見えますが、他の解答は違うアプローチを取っていました。特に、実際に問題を解くときは解答の後半にある

> 1と2の最小公倍数は2、
2と3の最小公倍数は6、
6と4の最小公倍数は12、
12と5の最小公倍数は60、
60と6の最小公倍数は60、
60と7の最小公倍数は420、
420と8の最小公倍数は840、
840と9の最小公倍数は2520

この考え方を使って、再帰でプログラムを書くことにしました。

### 最小公倍数と最大公約数

プログラムを書くにあたって、まず2つの自然数の最小公倍数を求める必要があります。

2つの自然数a, bの最大公約数をGCDとすると最小公倍数LCMは次の公式で求められます。[^1]

```math
LCM = \frac{a \times b}{GCD}
```

このため、まずは最小公倍数を求める必要があります。最小公倍数はユークリッド互除法で求めることができます。だいたい以下のように書けるかと思います。[^2]

```elixir
defmodule Problem5 do
  def gcd(a, b) do
    if rem(a, b) == 0 do
      b
    else
      gcd(b, rem(a, b))
    end
  end
end
```

Elixirに演算子`%`はないため、`rem`を使います。


上のプログラムを用いて、例えば824と128の最大公約数を求めたい場合は以下のようにします。

```elixir
IO.puts Problem5.gcd(824, 128) # 8
```

次に、先ほどの考え方を用いて最小公倍数を求めていきます。自分はこのように書きました。



```elixir
defmodule Problem5 do
  def gcd(a, b) do
    if rem(a, b) == 0 do
      b
    else
      gcd(b, rem(a, b))
    end
  end

  def solve(n, lcm, max) do
    if n == max do
      lcm
    else
      lcm_next = div(n * lcm, gcd(n, lcm))
      solve(n+1, lcm_next, max)
    end
  end
end
```

引数nに与えた自然数がmaxに到達するまでループします。Elixirでは、除算で整数値を返したい場合は`div`を使います。

```elixir
iex(1)> 6 / 2
3.0
iex(2)> div(6, 2)
3
```

これを用いて、問題の答えを求めると、

```elixir
IO.puts Problem5.solve(2, 1, 10) # 2520
IO.puts Problem5.solve(2, 1, 20) # 232792560
```

といったようになります。


## 感想

自分は普段再帰を使うことがほとんどなかったため、whileなどを使えず、再帰で書くことを求められるElixirは新鮮でした。今後はこのような考え方もスラスラできるようになっていきたいと思います。

### 追記

関数`gcd`や`solve`ですが、パターンマッチを使って以下のように書いたほうがいいかもしれませんね[^3]。 最初に書いたときよりもかなりすっきりしました。

```elixir
defmodule Problem5 do
  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x, y))

  def solve(max, lcm, max), do: lcm
  def solve(n, lcm, max) do
    lcm_next = div(n * lcm, gcd(n, lcm))
    solve(n+1, lcm_next, max)
  end
end
```

### さらに追記

コメントにてご指摘を頂いたのですが、今のままだと`Problem5.solve(2, 1, 11)`の計算結果が違いますね･･･。コメントでは修正版も教えていただいていますが、一応記事本文にも修正版を書いておきます。

```elixir
defmodule Problem5 do
  def gcd(x, 0), do: x
  def gcd(x, y), do: gcd(y, rem(x, y))

  def solve(max), do: solve(2, 1, max)
  def solve(max, lcm, max), do: div(max * lcm, gcd(max, lcm))
  def solve(n, lcm, max) do
    lcm_next = div(n * lcm, gcd(n, lcm))
    solve(n+1, lcm_next, max)
  end
end
```

地味に`solve/1`も追加してあります。こうしておくことで、

```elixir
IO.puts Problem5.solve(10) # 2520
IO.puts Problem5.solve(11) # 27720
IO.puts Problem5.solve(20) # 232792560
```

などと書けるようになります。これもコメントにて教えて頂いたものです。[mhgp](http://qiita.com/mhgp)さん、ありがとうございました！ :smile: 

---

[^1]: [C言語入門 - 入力した2つの自然数の最小公倍数を求める - Webkaru](http://webkaru.net/clang/find-lcm-of-two-number/) 
[^2]: 参考：[再帰版ユークリッドの互除法](http://www2.dokkyo.ac.jp/~grad0001/You/c/gcd2.html)
[^3]: 参考：[The Pragmatic Bookshelf | Programming Elixir](https://forums.pragprog.com/forums/322/topics/11926)