Project Eulerは、毎週末に1問プログラミングの問題が出題され、世界中でひそかにそれを早く解く競争が行われているサイトです。このサイトの問題を最初から解いていくと、自然にプログラミングや数学（主に数論）の力がついていきます。
ここではProject Eulerの問題を易しく解説していきます。高校生くらいに読んでもらって、数学やプログラミングの楽しみが伝わったらいいなあと思います。
言語は、基本的にPythonを使用します。Pythonがわからない人は、雰囲気だけでも読み取ってください。
Problem 1
（略）1000未満の自然数で3または5の倍数の総和を求めよ。
http://projecteuler.net/index.php?section=problems&id=1
問題文をそのままコードにすると次のようになるでしょうか。
N = 1000
s = 0
for n in range(1, N): # 1 - N-1
if n % 3 == 0 or n % 5 == 0:
s += n
print s
もっと数学よりのコーディングをするとこうかもしれません。
N = 1000
print sum(filter(lambda n: n % 3 == 0 or n % 5 == 0, range(1, N)))
しかし、これでは面白くありません。多くの場合、Project Eulerは、題意をそのままコードにしないほうが効率のよいものが書けます。
さて、これが次のような問題だったらどうでしょう。
1000未満の自然数で3の倍数の総和を求めよ。
一番小さい3の倍数は3で、次は6で、最後は999。総和は、
3 + 6 + ... + 999
ここで、
1 + 2 + ... + n = n(n + 1) / 2
を思い出すと、
3 + 6 + ... + 999 = 3 * (1 + 2 + ... + 333) = 3 * 333 * 334 / 2
と電卓レベルになりますね。同様に5の倍数の総和は、
5 + 10 + ... + 995 = 5 * (1 + 2 + ... + 199) = 5 * 199 * 200 / 2
だから、この2つを足し合わせれば、元の問題の答えになります。
さすがにこんなのにはひっかかりませんよね？図にすると、
Aを3の倍数の集合、Bを5の倍数の集合とします。
これを「ベン図」とか「オイラー図」と言います（ベン図とオイラー図は別のものですが、ここでは同じになるようです）。この問題が出題されたのは、この「オイラー図」を使いたかったからではないかと思われます。
この図でわかるように、上の考え方では、AとBの交わり、すなわち15の倍数の総和を2回足しています。ですから、この分を引いてやらないといけません。コードにすると、
# sum of multiples of d below n
def sum_sequence(d, n):
m = (n - 1) / d
return d * m * (m + 1) / 2N = 1000
print sum_sequence(3, N) + sum_sequence(5, N) - sum_sequence(15, N)
さて、この問題を一般化するとどうなるでしょうか。その前に今の問題を次のように言い換えてみましょう。
次回は、一般化した問題について考えます。
