Project Euler
http://projecteuler.net/index.php
存在を知ってはいたが、見たことはなかった。
最初から解いていこうと思う。
まず、Pythonで素直に書く。できれば数学的に考察した解も書く。
Q1.
3か5で割り切れる自然数で1000より小さいものの和。
a = filter(lambda x: x % 3 == 0 or x % 5 == 0, range(1000))
print reduce(lambda x, y: x + y, a)
mの倍数でnより小さいものの総和をSm,nと書くと、
p = [(n - 1) / m]
Sm,n = m + 2m + ... + pm
= (1 + p)mp/2
求める和は、
S3,1000 + S5,1000 - S15,1000
def sum(m, n):
p = (n - 1) / m
return (1 + p) * m * p / 2N = 1000
print sum(3, N) + sum(5, N) - sum(15, N)
