начать можно и без компьютера:
√2 = 1 + (√2-1) = 1 + 1/(√2+1) = 1 + 1 / (2+ (√2-1) ) =…
— видно, что процесс зациклился и дальше всё время будут выщелкиваться двойки,
√2 = [1, 2, 2, 2, 2, …]
для √3 лишь немногим сложнее:
1+(√3-1) → 1/2+√3/2 = 1 + (√3/2-1/2) → 1+√3 = 2+(√3-1) …
— всё снова зациклилось и √3 = [1, 1, 2, 1, 2, 1, 2, 1, 2…]
дальше уже всё-таки проще с компьютером… благо шаги этого процесса очень простые:
def step(x):
return (a:=floor(x)), 1/(x-a)
(первое возвращенное значение записываем в книжечку, второе — на место старого x, повторяем до полного удовлеторения)
можно заодно отловить период:
d=94
X, A = [x:=sqrt(d)], []
while not(x in X[:-1]):
a, x = step(x)
A += [a]
X += [x]
lp = X.index(x)
print(f"√{d} = [", *A[:lp], "(", *A[lp:], ") ]")
дает ответ
√94 = [ 9 ( 1 2 3 1 1 5 1 8 1 5 1 1 3 2 1 18 ) ]
почему для любой квадратичной иррациональности цепная дробь периодична — можно прочитать elsewhere (упражнение: доказать обратное утверждение — периодичная цепная дробь представляет собой квадратичную иррациональность; спойлер: неподвижная точка дробно-линейного преобразования является решением некоторого квадратного уравнения)
но когда смотришь на ответы для разных √d может броситься в глаза и еще кое-что: всегда получаются (почти) палиндромы (это доказал Галуа в своей первой работе)
простое упражение: изучить случай d=n²+1 (например, d=2026 : )
***
в коде выше скрыл такую подробность, что вычисления хочу производить в числах вида a+b√d — реализацию этого положу в комментарии (но не в этом суть)
***
уверен, что этот сюжет знаю из рассказов А.В.Спивака (хотя не нашел сейчас вполне подходящей ссылки), а сейчас коллега Гусарев про такое напомнил
***
ранее здесь про цепные дроби: https://t.me/compmathweekly/21