•
ペル方程式とは,
Dを平方数でない正の整数とするとき
x2−Dy2=1
の正の整数解x, yを求める問題をいう.
• Dが1けたの整数である場合は,x, yに様々な値を試してみると,短時間で1つの解が見つかる.
【例】
x2−2y2=1 → x=3, y=2
x2−3y2=1 → x=2, y=1
x2−5y2=1 → x=9, y=4
• 正の整数解のうちでxの値が最小のものx=a, y=bの組を最小解と呼ぶとき,一般に他の解は次の連立漸化式を満たす数列の一般項として表せることが知られている.
したがって,与えられたDの値に対して,最小解x=a, y=bを求めることが関心事となるが,Dが2桁以上の整数になると,最小解を見つけることが困難になって来る.
例えば,D=61の場合には,最小解のxは10桁の整数,yは9桁の整数となり,これよりも小さな解はない.
• このように,最小解を見つけること自体は,試し打ちになるので,コンピュータを使って網羅的に調査するのに適した仕事になる.
D=61, 97, 109のように途方もない計算になるものが含まれるので,初めはその数を避けるとよい.
== 1つの方程式で3秒以上要するものは,TimeOutとして放棄する ==
#1,#2 所要時間が3秒を超えるものはTimeOverとする
#3
だから,yが与えられたとき,xは
の整数部分と見てよい
#4 解が見つかれば (D, x, y)の形のタプルでリストに追加する
#5 Dの値の範囲を変更するには,#5の第2引数を変更する
#6 Dが平方数であればペル方程式にならないので除外する.
とその整数部分の差が0.0ならば平方数と見なす.
【例 2.1】
IDLE → New File → Save as .. → Run
import math as ma
import datetime as dt
dt1 = dt.datetime
sol_list = []
def pell1(D):
tn1 = dt1.now()
y = 1
while True:
tn2 = dt1.now()
if str(tn2-tn1) > '0:00:03': #1
sol_list.append((D,'TimeOver')) #2
return
x = int(ma.sqrt(D)*y+1) #3
if x**2 - D*(y**2) == 1:
sol_list.append((D,x,y)) #4
return
else:
y += 1
continue
for D in range(2, 200): #5
if ma.sqrt(D)-int(ma.sqrt(D)) == 0.0: #6
continue;
else:
pell1(D)
print(sol_list)
→
[(2, 3, 2), (3, 2, 1), (5, 9, 4), (6, 5, 2), (7, 8, 3), …
(59, 530, 69), (60, 31, 4), (61, 'TimeOver'), (62, 63, 8), …
(96, 49, 5), (97, 'TimeOver'), (98, 99, 10), (99, 10, 1),…
(106, 'TimeOver'), (107, 962, 93), (108, 1351, 130), (109, 'TimeOver'), …]
• D<200でTimeOverとなる値は
D=61, 97, 106, 109, 137, 139, 149, 151, 157, 163, 166, 172, 181, 191, 193, 199
• D<200でxが5桁以上になるものは,(D, x, y)の順に
(46, 24335, 3588)
(53, 66249, 9100)
(58, 19603, 2574)
(67, 48842, 5967)
(73, 2281249, 267000)
(76, 57799, 6630)
(85, 285769, 30996)
(86, 10405, 1122)
(89, 500001, 53000)
(93, 12151, 1260)
(94, 2143295, 221064)
(103, 227528, 22419)
(113, 1204353, 113296)
(118, 306917, 28254)
(124, 4620799, 414960)
(125, 930249, 83204)
(127, 4730624, 419775)
(129, 16855, 1484)
(131, 10610, 927)
(133, 2588599, 224460)
(134, 145925, 12606)
(154, 21295, 1716)
(161, 11775, 928)
(162, 19601, 1540)
(173, 2499849, 190060)
(177, 62423, 4692)
(179, 4190210, 313191)
(184, 24335, 1794)
(190, 52021, 3774)