1000未満の3の倍数と5の倍数の和

Project Euler 1

10未満の3もしくは5の倍数は3,5,6,9であり、その和は23になる。
では、1000未満の3もしくは5の倍数の総和は？

---

Project Euler の最初の問題は、Euler の名前にふさわしい問題だ。

単純に考えると以下の通りとなる。

# SAMPLE-1
N = 1000
x1 = 3
x2 = 5

ans = 0

for i in xrange(N):
    x = i
    if x % x1 == 0 or x % x2 == 0:
        ans = ans + x
print ans

さて、Euler の有名な伝説から 1 から 10 までの和の計算方法を考えてみる。

下図にあるように、1 から 10 までの総和は青色のブロックの個数である。
青色ブロックを上下さかさま（オレンジ色ブロック）にしてくっつけると 10×11の長方形となり、青色ブロックの個数は長方形の面積の半分に相当する。
したがって、1 + 2 + 3 + ･･･ + 8 + 9 = 10 × 11 / 2 = 55 となる。

これを応用し、3の倍数のブロックの個数の総和と5の倍数のブロックの総和を算出し、そこから最小公倍数である15のブロックの総和を減算する。

一般に N までの自然数のうち、x1 の倍数である自然数の個数は int(N / x1)であり、これが上図でいうところの青色ブロックの底辺の数になる。
次に高さであるが、最も N に近い x1 の倍数（これが上図の青色ブロックの高さに相当する）が int(N / x1) * x1 であることから、int(N / x1) * x1 + x1 となる。
したがって N 未満の x1 の倍数の合計は (int(N / x1) * (int(N / x1) * x1 + x1)) / 2 となる。

これらをまとめると、求めるべきプログラムは以下の通りとなる。

# SAMPLE-2
import fractions

N = 1000
x1 = 3
x2 = 5


def f(x):
    w = (N - 1) / x
    h = w * x + x
    return w * h / 2

print f(x1) + f(x2) - f(x1*x2/fractions.gcd(x1, x2))

なお、N の値が 1000 程度であれば、SAMPLE-1 と SAMPLE-2 の実行速度に（少なくとも体感的には）違いはない。
しかし、N = 100000000 程度にした場合、SAMPLE-2 の計算速度のほうが圧倒的に早い。