Project Euler Problem 12

Haskell 数学

About - Project Euler を解いていたのですが、久しぶりに数学的に考えた問題があったのでメモ。

Problem11までは力技で解けていたのですが、以下の問題は愚直に計算したらまったく終わらかったです。

問題は、簡単に言うと「三角数 で、約数の数が500を超える最小のものを求めよ」となります。
三角数とは、リンク先のWikipediaにもありますが、一般項が以下のような数列のことです。
F_n = \left\{ \begin{array}{ll} 1 & \text{(n=1)} \\ n + F_{n-1} & \text{(n>1)} \end{array} \right. = \sum^n_{k=1} k
これより、一般項は等差数列の和になっているので、結局以下のような一般項として考えることができます。
F_n = \frac{n(n+1)}{2}

さて、問題はこの F_n の約数の個数を求める必要があります。n は自然数なので、n もしくは n+1 のどちらかは偶数です。よって、F_nも自然数になります。
さらに、以下のことが成り立つ*1ので、2 F_nの約数の個数は nとn+1、それぞれの約数の個数をかけ合わせたものになります。
\forall n \in \mathbb{N}, \exists p \in \mathbb{N}, n \bmod p = 0 \wedge n+1 \bmod p = 0 \Rightarrow p = 1

ここまでくれば、あとはF_nの小さい方から順番に約数の個数を求めていけば、無事に解答を求めることができました。

Haskellでのコードは以下に。

module Main where

count_tri_divs n
    | even n    = (count_divs $ n `div` 2) * (count_divs $ n + 1)
    | otherwise = (count_divs n) * (count_divs $ (n + 1) `div` 2)

triangle n = (n * (n + 1)) `div` 2

count_divs n = length [1|x<-[1..n], n `mod` x == 0]

main = print $ triangle $ head $ filter ((>500).count_tri_divs) [1..]

*1:証明は背理法で簡単にできます。