Project Euler 100

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

Q100.
青いディスク15枚と赤いディスク6枚を用意して、ランダムに2枚取り出して両方青である確率は1/2である。このような組合せで最初に両方のディスクをあわせて1兆を超えるときの青いディスクの枚数。

青いディスクをm枚、赤いディスクをn枚とすると、

m/(m + n) * (m - 1)/(m + n - 1) = 1/2
m² - 2mn - n² - m + n = 0
a = (2m - 2n - 1)
b = 2n
a² - 2b² = 1

とペル方程式に帰着される。逆変換は、

m = (a + b + 1)/2
n = b/2

だから、aは奇数、bは偶数でなければならないが、常にそうなる。

N = 10 ** 12
a, b = 3, 2

while True:

    a, b = a * 3 + b * 4, a * 2 + b * 3

    m = (a + b + 1) / 2

    n = b / 2

    if m + n > N:

        print m

        break