読者です 読者をやめる 読者になる 読者になる

本当は怖い情報科学

情報系大学院生の趣味&実益ブログ。

[Project Euler] Project Euler Problem 12

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

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

まず、triangle numberは、ある整数nを用いて、
t = \frac{n(n+1)}{2}
と書ける。

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

さらに、nとn−1の必ずどちらかは偶数で、どちらかを2で割っても依然として互いに素である。よって、
F(\frac{n(n+1)}{2}) = F(\frac{n}{2})F(n+1) (nが偶数の時)
または
F(\frac{n(n+1)}{2}) = F(n)F(\frac{n+1}{2}) (nが奇数の時)
と表せる。

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

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

これらを実装すれば、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()
【広告】