Project Euler 78

プロジェクトオイラー
http://projecteuler.net/index.php

Q78.
nの分割数をP(n)とすると、P(n)が100万で割り切れる最も小さいn

分割数の求め方はWikipediaに載っている。
http://ja.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E5%88%86%E5%89%B2

from itertools import count
N = 10 ** 6
P = [ 1 ]

for n in count(1):

    s = 0

    for k in count(1):

        m = n - (3 * k * k - k) / 2

        if m < 0:

            break

        if k & 1:

            s += P[m]

        else:

            s -= P[m]

    for k in count(1):

        m = n - (3 * k * k + k) / 2

        if m < 0:

            break

        if k & 1:

            s += P[m]

        else:

            s -= P[m]

    s %= N

    P.append(s)

    if s == 0:

        print n

        break