Project Euler Problem 12

数学

これはかなりの良門ではないでしょうか。

約数の数が500以上になる最初の三角数を求めよ

三角数とは以下の式で書けるものです。
T(n) = \frac{1}{2}n(n+1)
Nの素因数分解が下のようになる時
N = p_1^{m_1}p_2^{m_2}\cdots p_n^{m_n}\qquad(p_1\le p_2\le\cdots p_n)
約数の個数は
F(n) = (m_1+1)(m_2+1)(m_3+1)\cdots
となります。また、互いに素な2数は指数が重複しないですから、
nが奇数なら
F(T(n)) = F(n)F<a href=
で偶数なら
F(T(n*1 = F(n/2)F(n+1)" src=http://www.texify.com/img/%5CLARGE%5C%21F%28T%28n%29%29%20%3D%20F%28n/2%29F%28n%2B1%29.gif align=center border=0>
です。従って、三角数の事はもう忘れて良くて、「自然数nのF(n)を求める方法」を考えれば良いです。
「よしじゃぁ、まず素数のテーブルを作って・・・」というのではダサいです。もっと調べて行きましょう。
まず、上で述べた事よりFは以下の漸化式を満たします。
F(p_1^{m_1}\cdots p_{n-1}^{m_{n-1}}p_n^{m_n}) = F(p_1^{m_1}\cdots p_{n-1}^{m_{n-1}})(m_n+1)
こういった素因数分解に基づく漸化式は、エラトステネスのふるいをちょっと変形させれば解けます。
従って後は、m_nを求める方法を考えれば良いです。整数nの素因数に素数pが何個含まれるかをG(n,p)と表すと、
G(np,p) = G(n,p)+1
という漸化式になりますから、小さいnから順番に求める事ができます。
以上をまとめると以下のコードになります。

N = 20000
sieve = Array.new(N+1, 1)
exp = Array.new(N+1)
2.upto(N) do |n|
    if sieve[n] == 1 then
        exp.fill(0)
        n.step(N, n) do |k|
            exp[k] = exp[k/n] + 1
            sieve[k] *= (exp[k] + 1)
        end
    end
    r = (n % 2 == 0) ? sieve[n/2]*sieve[n-1] : sieve[n]*sieve[(n-1)/2]
    if r >= 500 then
        puts n*(n-1)/2
        exit
    end
end

実行時間は0.16秒くらいでした。

*1:n+1)/2)" src=http://www.texify.com/img/%5CLARGE%5C%21F%28T%28n%29%29%20%3D%20F%28n%29F%28%28n%2B1%29/2%29.gif align=center border=0> で偶数なら