no-image

プロジェクトオイラーを解く!!

[mathjax]$$e^{i\pi}+1=0$$

この世で最も美しいと言われる公式。

それを発見したのは大数学者レオンハルト・オイラー。いや、ほんとすごい人なんですってば。

「発散する関数の値も求められないようでは人間じゃない(誇大表現)」

オイラーの素晴らしさについて語っているととてもこの記事が終わりそうにないので詳しくはググるなりなんなりで調べてみてください。

今回はそんな彼の名前がつけられたプロジェクトオイラーにチャレンジしてみましょう。

プロジェクトオイラーって?

プロジェクト・オイラー(英: Project Euler、名称はレオンハルト・オイラー由来)は、数学やプログラミングなどに興味を持つ大人や学生が主な利用者であり、プログラミング (コンピュータ)による一連の計算問題の解決を目的としたウェブサイトである。 400以上[2]の問題の他に毎週末毎に1問ずつ増えており、様々な難問が用意されているが、 一般的なスペックのパソコンで効率的なアルゴリズムを用いれば、いずれも1分未満で解ける。 正答回答者のみが各問題の掲示板を閲覧できる[3]。 2001年に創設されて以来世界的な知名度と人気を得ており、2013年10月の時点では世界中から34万人以上の利用者(最低1問以上の正答者)を有する[4]。 利用者は正答数に応じて最大16のレベルが振り分けられ、各々の進捗状況を確認できる。

詳しくはウィキペディアで。

Problem 1 Multiples of 3 and 5

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.

Python
sum = 0
for i in range(1, 1000):
    if i % 15 == 0:
        sum = sum + i
        continue
    if i % 3 == 0 or i % 5 == 0:
        sum = sum + i
print(sum)

愚直に1000回ループするコードを書くとこうなる。

最初に15で割り切れた場合はその数を足し、以降の処理をcontinueでスキップする。

15で割り切れず、3か5で割り切れた場合はその数を足す。

これはつまり3の倍数と5の倍数を足していることと等価である。

プログラムを書くときはこんな感じで等価な数学的処理を考えてそれをコードにするという作業が必要になってくる。もちろん難しいのは前者である。

Python
import numpy as np


def Sum(k, m):
    n = np.floor((m - 1) / k)
    return int(k * n * (n + 1) / 2)


if __name__ == "__main__":
    sum = Sum(3, 1000) + Sum(5, 1000) - Sum(15, 1000)
    print(sum)

包除原理を利用することでより効率的なコードが書ける。

これならばnの値(今回の場合は1000)がどんどん大きくなっても高速に解を求められる。

特に素数を探すような問題ではこのような高速化が必要になってくる。

Problem 2 Even Fibonacci numbers

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.

python
import numpy as np


def Fibo(n):
    phi = (1 + np.sqrt(5)) / 2
    fibo = np.ceil(np.power(phi, n + 1) / np.sqrt(5) - 1 / 2)
    return int(fibo)


if __name__ == "__main__":
    n = 0
    sum = 0
    while Fibo(n) <= 4000000:
        if Fibo(n) % 2 == 0:
            sum = sum + Fibo(n)
        n = n + 1
    print(sum)

ちょっとセコいコードになりました。

フィボナッチ数列は単純に実装すると前2つの値の和を返すという関数を実装すればいいのですが、そうすると再帰的に関数を呼び出す必要があり、インタプリタ型言語であるPythonだと処理速度が著しく遅くなってしまいます。

そこでフィボナッチ数列の一般項を使うことでパッと求めてしまいます。

[mathjax]
$$F_n=\frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2}\right) ^n – \left( \frac{1-\sqrt{5}}{2}\right) ^n\right\}$$

ここで

[mathjax]
$$\phi = \frac{1+\sqrt{5}}{2}$$

とは黄金比と呼ばれる値です。

そしてこの式の第二項は1よりも小さい値をn乗するので

[mathjax]

$$n=0$$

のときに最大値をとり、その値は

[mathjax]

$$\frac{1}{\sqrt{5}} \approx 0.447$$

となります。

つまり、第二項を省略したとしてもフィボナッチ数の真の値から高々0.447程度しか(上に)ズレていない値が求められるということです。

したがって、

[mathjax]
$$F_n = \left\lceil \frac{\phi^n}{\sqrt{5}} – \frac{1}{2} \right\rceil $$

で正確な値が求められます。

あとはそれが2で割れるかどうかを調べて、割れたら足していくというコードを書けば完成です。

残りの問題は?

ちまちま解いていこうと思います。

実は過去に登録していたことがあってCとかC++ではチャレンジしたことがあったりなかったり(笑)