僕のYak Shavingは終わらない

車輪の再発明をやめたらそこには壮大なYakの群れが

ProjectEuler 001-2 倍数の和を数学的に求める

そういえば問題001ですが実は数学的に計算可能ですね。

もう一度問題

Problem 1 †
10未満の自然数のうち、3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり、 これらの合計は 23 になる。
同じようにして、1,000 未満の 3 か 5 の倍数になっている数字の合計を求めよ。

ということで計算してみよう。

まずは23の方で求める。

等差級数の公式より計算する。
10未満の3の倍数は3,6,9であるが
これは初項3、末項9、項数3の等差級数であるので
\frac{3(3 + 9) }{2} = 18
同様に10未満の5の倍数は5であるのでこの場合は
18 + 5 = 23
となり答えが求められた。 

なのですがこれだとたまたまうまくいってしまっているのですが、数が大きくなるともっと考慮が必要です。
もう少し数を増やして20未満までの自然数としてみましょう。

20未満の自然数のうち3と5の倍数の和は
3, 5, 6, 9, 10, 12, 15, 18 の和であるので、78
今度は先ほどと同じように3の倍数の等差級数と5の倍数の等差級数を考えその和を計算してみる。
\frac{6(3 + 18) }{2} + \frac{3(5 + 15)}{2} = 63 + 30 = 93
となり本来の答えよりも大きい。

これは20未満の3の倍数と5の倍数の等比級数に重複があるためです。
3の倍数:3, 6, 9, 12, 15, 18
5の倍数:5, 10, 15
であるので15が重複していることがわかります。

つまり3と5の倍数である15が2度加算されているのが問題です。
今回は15を1回引くだけでいいのですが、念のためこの15を公式を使って求めましょう。
\frac{1(15 + 15)}{2} = 15

であるため、20未満の3と5の倍数の和は以下となることがわかります。
{3の倍数の等比級数の和} + {5の倍数の等比級数の和} - {15の倍数の等比級数の和} = 63 + 30 - 15 = 78

はい、とうことでこれで一般的な求め方がわかると思います。

これをプログラムにすると

p( (999.div(3) * (3 + 999) + 999.div(5) * (5 + 995) - 999.div(15) * (15 + 990)) / 2)

1000未満の数である999をそれぞれの倍数で割った時の商(div)が項数となります。割る2は括弧の外に出しました。

こんな感じで数学だけで求めることもできます。
そのため総当り計算(Blute Force)をするよりも速く解けることが多いです。

そんな感じで幅広い解き方があるのがおもしろいですね。

ということで今回はこれまで。

ではでは〜