ペル方程式の解の列挙方法 - まめめもProject Euler 66 のネタバレです。見たくない人は見ないでください。本質的には全然理解できてないですが、それなりに有用な情報だと思ったので、解き方だけメモします。 ペル方程式とは (ただし D は平方数でない自然数) という形の不定方程式をペル方程式というそうです。 これを満たす整数 x と y は無数にあります。ですが、D の値によっては最小解でもかなり大きい値になることがあり、1 から順番に探していくことは事実上不可能です。たとえば D = 166 のときは以下が最小解です。 p(1700902565**2 - 166 * 132015642**2) #=> 1 最小解の見つけ方 最小解を高速に探し出す方法があります (参考: 二次無理数の連分数展開とペル方程式の解の構成) 。D の平方根の連分数表示を使って、漸化式で解けるとのこと。 例えば、14 の平方根の連分数表示は
