数多く割り切れる三角数

Project Euler 12

三角数の数列は、自然数を加算して生成されるものである。7番目の三角数は $1+2+3+4+5+6+7=28$ である。最初の $10$ 項は、以下の通りとなる。 \[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ･･･\] 最初の $7$ 項の約数を列挙する。

 1:1
 3:1,3
 6:1,2,3,6
10:1,2,5,10
15:1,3,5,15
21:1,3,7,21
28:1,2,4,7,14,28

$28$ は約数の数が $5$ を超える最初の三角数である。
最初に約数の数が $500$ を超える三角数はいくつか？

---

ある自然数 $n$ に対して、素因数分解を $n = p_1^{e_1}\times p_2^{e_2}\times … \times p_n^{e_n}$ としたとき、$n$ の約数の個数は $(e_1+1)\times(e_2+1)\times … \times(e_n+1)$ となる。
そこで、まず素因数分解用の関数を作成する。

def get_prime():
    yield 2
    prime_list = [2]
    i = 3
    while True:
        for p in prime_list:
            if i % p == 0:
                break
        else:
            prime_list.append(i)
            yield i
        i += 2

def factorize(n):
    l = []
    for i in get_prime():
        if i*i > n:
            break
        x = 0
        while n % i == 0:
            x += 1
            n /= i
        if x != 0:
            l.append((i, x))
    if n != 1:
        l.append((n, 1))
    return l

factorize は 自然数 $n$ を素因数分解し、(素因数, べき乗数) のリストを返す。
これを利用して、約数の個数を得る関数を作成する。

def get_numof_divisor(n):
    r = 1
    for fc in factorize(n):
        r *= fc[1] + 1
    return r

get_numof_division 関数は factorize 関数で得られるべき乗数を用いて、約数の個数を算出する。
これらを用いて、約数の個数が $500$ を超過する三角数を算出する。

def triangular_number(n):
    return n * (n+1) / 2


t = triangular_number(1)
r = get_numof_divisor(t)
while r < 500:
    print t, r
    i += 1
    t = triangular_number(i)
    r = get_numof_divisor(t)
print t, r