# オイラー先生からの挑戦状！（宮崎の解答）
[[オイラー先生からの挑戦状！]]
数学なので Haskell で書きました！
（だいぶ忘れてる）
## Problem 1
[#1 Multiples of 3 or 5 - Project Euler](https://projecteuler.net/problem=1)
```
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
```
### 今回の解答
```haskell
main = print $ sum $ takeWhile (< 1000) [n | n <- [1..], n `mod` 3 == 0 || n `mod` 5 == 0]
```
Python でも使えるリスト内包表記を使っています。
Haskell は遅延評価なので、 `[1..]` のような無限配列を扱うことができます。
あとは、おとなしくリスト内包表記の条件に「 3 と 5 で割り切れること」を指定。
### 過去の解答
```haskell
main = print $ s (*3) + s (*5) - s (*15)
s = sum . takeWhile (< 1000) . flip map [1..]
```
「3 の倍数の和」と「5 の倍数の和」を足して、「15 の倍数の和」を引くというアプローチ。
Haskell には `flip` という引数の順番をひっくり返してくれる便利関数があります。
```haskell
s = sum . takeWhile (< 1000) . flip map [1..]
s f = sum . takeWhile (< 1000) $ map f [1..]
```
ひっくり返さずに書くと、下のようになります。
引数が最後に持ってくると関数定義に引数を省略できます。
## Problem 2
[#2 Even Fibonacci numbers - Project Euler](https://projecteuler.net/problem=2)
```
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
```
### 今回の解答
おとなしくフィボナッチ数列を求めて、そこから偶数だけ取り出してもいいのですが…
下のように偶数のものに印をつけると、規則性が見えてきますね。
（ `0` から始まるようにしました）
$
(0), 1, 1, (2), 3, 5, (8), 13, 21, (34), 55, 89, (114) \ldots
$
具体的にはこんな感じ。
$
\begin{align}
&8 = 2 \times 4 + 0 \\
&34 = 4 \times 8 + 2 \\
&144 = 4 \times 34 + 8 \\
\end{align}
$
これを一般項で表すと。
$
a_n = 4 \times a_{n-1} + a_{n-2}
$
こういう数列です。
$
0, 2, 8, 34, 114, \ldots
$
コードで書くと。
```haskell
main = print $ fibEvenSum 4000000
fibEvenSum :: Int -> Int
fibEvenSum cap = sum $ takeWhile (< cap) fibEvenList
fibEven :: Int -> Int
fibEven 0 = 0
fibEven 1 = 2
fibEven n = 4 * fibEvenList !! (n - 1) + fibEvenList !! (n - 2)
fibEvenList :: [Int]
fibEvenList = map fibEven [0..]
```
関数の再起呼び出しになります。
しかし、普通にやると計算量が増えてしまいます。
そこで、上のコードでは一度計算した結果をリストに保存（メモ化）しています。
### 過去の解答
全然覚えてなくて、ひさしぶりに見て理解に時間がかかりました。
```haskell
main = print $ sum . filter even . takeWhile (< 4000000) $ fib
fib = scanl (+) 1 (1:fib)
```
Haskell にはループ構文がなくて、 Ruby でいう `Enumerable` で処理します。
[module Enumerable (Ruby 3.2 リファレンスマニュアル)](https://docs.ruby-lang.org/ja/latest/class/Enumerable.html)
上のコードで使っている `scanl` は「畳み込み」の関数の一種です。
「畳み込み」というと、 Ruby では `inject` や `reduce` （実態はどっちも同じ）です。
LISP など関数型言語だと `fold` と呼ぶことが多いと思います。
`scanl` は畳み込んでひとつの値を求めるのではなく、その過程をリストに残します。
図解するとこんな感じ。（図はパクってきました）
![[scanl.png]]
上記コードを有限リストで書いてみます。
そうすると、こんなイメージ。
```haskell
fib = scanl (+) 1 [1, 1, 2, 3, 5]
[1, 1+1]
[1, 2, 2+1]
[1, 2, 3, 3+2]
[1, 2, 3, 5, 5+3]
[1, 2, 3, 5, 8]
```
途中まで無限、途中から有限にしてみましょう。
```haskell
fib = scanl (+) 1 (1:fib)
scanl (+) 1 (1:(scanl (+) 1 (1:fib)))
scanl (+) 1 (1:(scanl (+) 1 (1:(scanl (+) 1 (1:fib)))))
-- キリがないのでここで止めて畳み込み
scanl (+) 1 (1:(scanl (+) 1 (1:[1])))
scanl (+) 1 (1:(scanl (+) 1 [1, 1]))
scanl (+) 1 (1:[1, 2, 3])
scanl (+) 1 [1, 1, 2, 3]
[1, 2, 3, 5, 8]
```
### 参考
フィボナッチ数列には一般項（ビネの公式）があります。
$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)$
実際には、ド・モアブルやオイラー先生が先に発表してるので、ビネが最初の発見者ではないそうです。
（ちなみに、「科学的発見に第一発見者の名前がつくことはない」という「スティグラーの法則」というものがあります。例えば「ピタゴラスの定理」は古代バビロニアでも知られていたとか）
数式だと「$\mathcal{O}(1)$ で解ける！」ように見えますが、コンピューターで計算するとそう簡単ではないですね。
$\sqrt {5}$ をどうするか問題もある。
## さいごに
### Poroject Euler に取り組む
プログラミングだけの観点で言うと、下のような注意点が必要だと思います。
- オーダー $\mathcal{O}$ に気を付ける
- 再帰呼び出しはシンプルに書けるけど、スタックオーバーフローに気を付ける
- ループ構文で書く
- 末尾呼び出し最適化のある処理系なら末尾再帰の形にする
- そもそも数学的に解いて、計算をコンピューターに任せる
- 手続型アプローチでは後に進むにつれてつらくなるらしい
### 関数型言語的、宣言的アプローチ
関数型言語は最初にリストを用意して、それを加工していくというイメージ。
思考方法が変わるので触りだけでも体験するといいかもです。
Rails 開発する時にも、個人的には関数型アプローチで「宣言的に」記述することを心がけています。
そうすると可読性が上がること、モジュール化が進むこと、ユニットテストがしやすくなることが期待できます。
[Imperative vs Declarative Programming](https://ui.dev/imperative-vs-declarative-programming)
> IMPERATIVE (HOW)
> I see that table located under the Gone Fishin’ sign is empty. My husband and I are going to walk over there and sit down.
> DECLARATIVE (WHAT)
> Table for two, please.
### Excuse
植物の色素を作るタンパク質を研究していた生物学出身者が書いてるので、情報学部出身の方のツッコミお待ちしております。