Project Euler 1 - Essaytial Machine Learning

問題

　 $N \in \mathbb{N}$ 未満の3または5の正倍数の総和を $PE1(N)$ とおいた時 $PE1(1000)$ を求める。

記号

[ 表記 ]：[ 返り型 ]：[ 説明 ]
$p \vert n$ ：真偽値： $n$ は $p$ の倍数
$\mathrm{LCM}(p, q)$ ：正整数： $p$ と $q$ の最小公倍数
$y // x$ ：整数：切り捨て除算、 $y / x$ を超えない最大の整数

解法

　 $N$ 未満の $p$ の倍数の集合を $M(p, N)$ とおく：

$\displaystyle M(p, N) := \{ n \in \mathbb{N} \ | \ p \vert n, \ n \lt N \}.$

この時 $PE1(N) = \sum_{i \in M(3, N) \cup M(5, N)} i$ で、これは $M(3, N)$ と $M(5, N)$ それぞれの要素の総和から重複する要素、つまり $M(3, N) \cap M(5, N)$ の要素の総和を引いたものに等しい*1。また、

$\displaystyle M(3, N) \cap M(5, N) = M(\mathrm{LCM}(3, 5), N) = M(15, N)$

で、 $M(p, N)$ の要素の総和は

$\displaystyle \sum_{i \in M(p, N)}i = \sum_{i=1}^{(N-1)//p}pi = \frac{1}{2}p( (N-1)//p)( (N-1)//p+1)$

となるので、簡単のため $N\vert_p := (N-1)//p$ と書くと、

$\displaystyle \begin{align} PE1(N) & = \sum_{i \in M(3, N)}i+\sum_{i \in M(5, N)}i-\sum_{i \in M(15, N)}i \\ & = \frac{1}{2}(3N\vert_3(N\vert_3+1)+5N\vert_5(N\vert_5+1)-15N\vert_{15}(N\vert_{15}+1) ). // \end{align}$

　ここからもう少し簡約化したかったが、特に思い付かなかった。 $N-1 = 15q+r$ （ $r \lt 15$ ）と書いて $N\vert_p$ を $q$ 、 $r$ で置き替えると

$\displaystyle PE1(N) = \frac{15}{2}q(7q+1+2(r//3+r//5) )+PE1(r+1)$

ぐらいにはなる。手計算だと少し楽だが、機械にやらせる分には $N\vert_3$ 、 $N\vert_5$ を消去したのが $r//3$ 、 $r//5$ の計算で清算される。

解

$\displaystyle PE1(1000) = \frac{1}{2}(3 \cdot 333 \cdot 334+5 \cdot 199 \cdot 200-15 \cdot 66 \cdot 67 ) = 233168.$

*1:この辺の総和の集合を使った表記と式変形のきちんとした話を知らないので恐る恐るになるのがアレ。