[Project Euler] Project Euler Problem 12

Pythonで実装。おそらく、安直に書くと計算が終わらない最初の問題かも？

引数の数が500を超える最初のtriangle numberは何か？という問題。

まず、triangle numberは、ある整数ｎを用いて、

と書ける。

ここで、ｎとｎ+１は互いに素であることに注目しよう。一般に、ある整数ｎの約数の数をF(n)と表現することにすると、ｎとｍが互いに素なら

である。

さらに、ｎとｎ−１の必ずどちらかは偶数で、どちらかを２で割っても依然として互いに素である。よって、
　（ｎが偶数の時）
または
　（ｎが奇数の時）
と表せる。

普通なら、分解されたF(n)等は真面目に計算するしかないが、ここでは二つの工夫をすることによって計算量を劇的に減らすことが出来る。

1. 一度計算した約数の個数は、保存しておいて再利用する
2. もし、ｎや(ｎ+１)/２等の数が、再び ｍ(ｍ+１)のかたちで表せるなら、前出の式が再び適用できる（このパターンは意外に多い）

これらを実装すれば、Pythonで書いても計算は一瞬で終わる。というわけでソースコード。

import math
import sys

fact = {1:1, 2:2} # 約数の個数をキャッシュする辞書

def num_factors(n):
    if n in fact: return fact[n]

    r = int(math.sqrt(n))

    num = 0
    if r * (r+1) == n:
        num = num_factors(r) * num_factors(r+1)
    else:
        i = 1
        while i < r:
            if n % i == 0:
                num += 1

            i += 1

        num *= 2
        if r*r == n: num += 1

    fact[n] = num
    return num

def main():
    n = 2
    while True:
        if n % 2 == 0:
            fn = num_factors(n/2) * num_factors(n+1)
        else:
            fn = num_factors(n) * num_factors((n+1)/2)

        if fn >= 500:
            print "%d = (%d * %d)/2, it has %d factors" % (n*(n+1)/2, n, n+1, fn)
            return

        fact[n * (n+1)/2] = fn

        n += 1

if __name__ == '__main__':
    main()