ScalaでProject Euler（147）

Problem 100

ラストです。
合計のディスクの枚数をn、青いディスクの枚数をbとすると、

(b/n)( (b-1)/(n-1)) = 1/2

です。変形していくと次のようになります。

(2n - 1)² - 2(2b - 1)² = -1

これはPell方程式ですね。

x² - 2y² = -1

の解は、

x + y√2 = (1 + √2)^2m+1

と書けます。隣の解、(x_m, y_m)と(x_m+1, y_m+1)の関係は、

(x_m+1, y_m+1) = (3x_m + 4y_m, 2x_m + 3y_m)

となります。常に共に奇数となることがわかりますね。