周期連分数

数学において、無限周期連分数とは、次のような形で表される 単純な連分数である。

${\displaystyle x=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{\quad \ddots \quad a_{k}+{\cfrac {1}{a_{k+1}+{\cfrac {\ddots }{\quad \ddots \quad a_{k+m-1}+{\cfrac {1}{a_{k+m}+{\cfrac {1}{a_{k+1}+{\cfrac {1}{a_{k+2}+{\ddots }}}}}}}}}}}}}}}}}}$

ここで、 k +1 個の部分分母の最初のブロックの後に、無限に繰り返されるm個の部分分母のブロックが続きます。たとえば、は周期連分数 に展開できます。 ${\displaystyle [a_{0};a_{1},\dots ,a_{k}]}$${\displaystyle [a_{k+1},a_{k+2},\dots ,a_{k+m}]}$${\displaystyle {\sqrt {2}}}$${\displaystyle [1;2,2,2,...]}$

この記事では、周期的な正則連分数の場合のみを扱います。言い換えれば、この記事の残りの部分では、すべての分母a _i ( i ≥ 1) が正の整数であると仮定します。分母a _iが任意の実数または複素数である 一般的なケースは、収束問題の記事で扱われます。

通常の連分数のすべての部分分子は1に等しいので、上記の連分数は次のように表記できる。

${\displaystyle {\begin{aligned}x&=[a_{0};a_{1},a_{2},\dots ,a_{k},a_{k+1},a_{k+2},\dots ,a_{k+m},a_{k+1},a_{k+2},\dots ,a_{k+m},\dots ]\\&=[a_{0};a_{1},a_{2},\dots ,a_{k},{\overline {a_{k+1},a_{k+2},\dots ,a_{k+m}}}]\end{aligned}}}$

ここで、2行目のビンキュラムは繰り返しブロックを示す。^[1]一部の教科書では 、

${\displaystyle {\begin{aligned}x&=[a_{0};a_{1},a_{2},\dots ,a_{k},{\dot {a}}_{k+1},a_{k+2},\dots ,{\dot {a}}_{k+m}]\end{aligned}}}$

ここで、繰り返しブロックは最初の項と最後の項の上に点で示されます。^[2]

最初の非繰り返しブロックが存在しない場合、つまりk = -1の場合、a ₀ = a _mであり、

${\displaystyle x=[{\overline {a_{0};a_{1},a_{2},\dots ,a_{m-1}}}],}$

正則連分数x は純粋に周期的であると言われています。たとえば、黄金比φの正則連分数は純粋に周期的ですが、の正則連分数は周期的ですが純粋に周期的ではありません。 ${\displaystyle [1;1,1,1,\dots ]}$${\displaystyle [1;2,2,2,\dots ]}$${\displaystyle {\sqrt {2}}}$

周期的連分数は実数2次無理数と1対1に対応しています。この対応はミンコフスキーの疑問符関数によって明示的に提供されます。その記事では、このような連分数を簡単に扱えるツールも紹介しています。まず、純粋に周期的な部分について考えてみましょう。

${\displaystyle x=[0;{\overline {a_{1},a_{2},\dots ,a_{m}}}],}$

これは実際には次のように書くことができる。

${\displaystyle x={\frac {\alpha x+\beta }{\gamma x+\delta }}}$

は整数であり、を満たす。明示的な値は次のように記述することで得られる。 ${\displaystyle \alpha,\beta,\gamma,\delta}$${\displaystyle \alpha \delta -\beta \gamma =1.}$

${\displaystyle S={\begin{pmatrix}1&0\\1&1\end{pmatrix}}}$

これは「シフト」と呼ばれ、

${\displaystyle S^{n}={\begin{pmatrix}1&0\\n&1\end{pmatrix}}}$

同様に、

${\displaystyle T\mapsto {\begin{pmatrix}-1&1\\0&1\end{pmatrix}}}$

となる。これらの行列は両方ともユニモジュラ行列であり、任意の積はユニモジュラのままである。そして、上記のように与えられると、対応する行列は^[3]の形になる。${\displaystyle T^{2}=I}$${\displaystyle x}$

${\displaystyle S^{a_{1}}TS^{a_{2}}T\cdots TS^{a_{m}}={\begin{pmatrix}\alpha &\beta \\\gamma &\delta \end{pmatrix}}}$

そして1つは

${\displaystyle x=[0;{\overline {a_{1},a_{2},\dots ,a_{m}}}]={\frac {\alpha x+\beta }{\gamma x+\delta }}}$

明示的な形式として。行列の要素はすべて整数なので、この行列はモジュラー群に属する。 ${\displaystyle SL(2,\mathbb {Z} ).}$

二次無理数は二次方程式の無理実根 である。

${\displaystyle ax^{2}+bx+c=0}$

ここで係数a、b、cは整数であり、判別式、は0より大きい。二次方程式の公式により、あらゆる二次無理数は次のように表される 。${\displaystyle b^{2}-4ac}$

${\displaystyle \zeta ={\frac {P+{\sqrt {D}}}{Q}}}$

ここで、P、D、およびQは整数、D > 0 は完全な平方数ではない（ただし、必ずしも平方数ではない）、Q は量を割り切ります（たとえば）。このような二次無理数は、二次無理数で説明したように、平方数のない数の平方根（たとえば ）を使用して別の形式で表すこともできます。 ${\displaystyle P^{2}-D}$${\displaystyle (6+{\sqrt {8}})/4}$${\displaystyle (3+{\sqrt {2}})/2}$

周期連分数の完全な商を考慮することにより、オイラーはxが規則的な周期連分数であればx は2 次無理数であることを証明できました。証明は簡単です。分数自体から、 x が満たさなければならない整数係数を持つ 2 次方程式を構築できます。

ラグランジュはオイラーの定理の逆を証明した。つまり、x が2 次無理数であれば、xの正則連分数展開は周期的である。^[4] 2 次無理数xが与えられたとき、それぞれが同じ判別式を持ち、 xの正則連分数展開の連続する完全商を互いに関連付けるm個の異なる 2 次方程式を構築できる。このような方程式は有限個しかないため (係数は有界である)、 x を表す正則連分数の完全商 (および部分分母) は最終的に繰り返される必要がある。

二次無理数は 、その共役数が 不等式 を満たす場合、既約であると言われます。たとえば、黄金比は1 より大きく、共役数が-1 より大きく 0 より小さいため、既約無理数です。一方、2 の平方根は1 より大きいですが、共役数が -1 より小さいため、既約無理数ではありません。 ${\displaystyle \zeta ={\frac {P+{\sqrt {D}}}{Q}}}$${\displaystyle \zeta >1}$ ${\displaystyle \eta ={\frac {P-{\sqrt {D}}}{Q}}}$${\displaystyle -1<\eta <0}$${\displaystyle \phi =(1+{\sqrt {5}})/2=1.618033...}$${\displaystyle (1-{\sqrt {5}})/2=-0.618033...}$${\displaystyle {\sqrt {2}}=(0+{\sqrt {8}})/2}$${\displaystyle -{\sqrt {2}}=(0-{\sqrt {8}})/2}$

ガロワは、2次無理数ζを表す通常の連分数が純粋に周期的であるのは、ζが既約無理数である場合のみであることを証明した。実際、ガロワはそれ以上のことを示した。彼はまた、ζが既約2次無理数でηがその共役である場合、ζの連分数と(−1/η)の連分数は両方とも純粋に周期的であり、それらの連分数の1つの繰り返しブロックは、もう1つの繰り返しブロックの鏡像であることを証明した。記号では、

${\displaystyle {\begin{aligned}\zeta &=[{\overline {a_{0};a_{1},a_{2},\dots ,a_{m-1}}}]\\[3pt]{\frac {-1}{\eta }}&=[{\overline {a_{m-1};a_{m-2},a_{m-3},\dots ,a_{0}}}]\,\end{aligned}}}$

ここでζは任意の約数二次無理数であり、ηはその共役数である。

ガロアのこれら2つの定理から、ラグランジュがすでに知っていた結果が導き出される。r  > 1が完全な平方数ではない有理数である場合、

${\displaystyle {\sqrt {r}}=[a_{0};{\overline {a_{1},a_{2},\dots ,a_{2},a_{1},2a_{0}}}].}$

特に、n が任意の非平方の正の整数である場合、√ nの通常の連分数展開には長さmの繰り返しブロックが含まれ、その中で最初のm − 1 個の部分分母が回文文字列 を形成します。

組み合わせの順序を分析することで

${\displaystyle {\frac {P_{n}+{\sqrt {D}}}{Q_{n}}}}$

を通常の連分数として展開したときに起こり得る問題について、ラグランジュは、展開における最大の分母a _{i が}未満であり、繰り返しブロックの長さが 2 D未満であることを示しました。 ${\displaystyle \zeta ={\frac {P+{\sqrt {D}}}{Q}}}$${\displaystyle 2{\sqrt {D}}}$

最近では、除数関数に基づくより鋭い議論^{[5] [6] [7]により、}判別式Dの2次無理数の繰り返しブロックの長さは、 ${\displaystyle {\mathcal {O}}({\sqrt {D}}\ln {D}).}$

次の反復アルゴリズム^[8]は、標準形の連分数展開を得るために使用できる（Sは完全な平方数ではない任意の自然数である）。

${\displaystyle m_{0}=0\,\!}$

${\displaystyle d_{0}=1\,\!}$

${\displaystyle a_{0}=\left\lfloor {\sqrt {S}}\right\rfloor \,\!}$

${\displaystyle m_{n+1}=d_{n}a_{n}-m_{n}\,\!}$

${\displaystyle d_{n+1}={\frac {S-m_{n+1}^{2}}{d_{n}}}\,\!}$

${\displaystyle a_{n+1}=\left\lfloor {\frac {{\sqrt {S}}+m_{n+1}}{d_{n+1}}}\right\rfloor =\left\lfloor {\frac {a_{0}+m_{n+1}}{d_{n+1}}}\right\rfloor \!.}$

m _n、d _n、a _{n は}常に整数であることに注意してください。この3つ組が以前に遭遇したものと同じである場合、アルゴリズムは終了します。また、 a _i = 2 a ₀の場合、アルゴリズムはa _{iで終了することもできます。} ^[9]これは実装が簡単です。

それ以降は展開が繰り返されます。シーケンスは連分数展開です。 ${\displaystyle [a_{0};a_{1},a_{2},a_{3},\dots ]}$

${\displaystyle {\sqrt {S}}=a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\,\ddots }}}}}}}$

√ 114 を連分数として得るには、 m ₀  = 0、d ₀  = 1、a ₀  = 10 から始めます (10 ²  = 100、11 ²  = 121 > 114 なので 10 を選択します)。

${\displaystyle {\begin{aligned}{\sqrt {114}}&={\frac {{\sqrt {114}}+0}{1}}=10+{\frac {{\sqrt {114}}-10}{1}}=10+{\frac {({\sqrt {114}}-10)({\sqrt {114}}+10)}{{\sqrt {114}}+10}}\\&=10+{\frac {114-100}{{\sqrt {114}}+10}}=10+{\frac {1}{\frac {{\sqrt {114}}+10}{14}}}.\end{aligned}}}$

${\displaystyle m_{1}=d_{0}\cdot a_{0}-m_{0}=1\cdot 10-0=10\,.}$

${\displaystyle d_{1}={\frac {S-m_{1}^{2}}{d_{0}}}={\frac {114-10^{2}}{1}}=14\,.}$

${\displaystyle a_{1}=\left\lfloor {\frac {a_{0}+m_{1}}{d_{1}}}\right\rfloor =\left\lfloor {\frac {10+10}{14}}\right\rfloor =\left\lfloor {\frac {20}{14}}\right\rfloor =1\,.}$

したがって、m ₁  = 10、d ₁  = 14、a ₁  = 1 です。

${\displaystyle {\frac {{\sqrt {114}}+10}{14}}=1+{\frac {{\sqrt {114}}-4}{14}}=1+{\frac {114-16}{14({\sqrt {114}}+4)}}=1+{\frac {1}{\frac {{\sqrt {114}}+4}{7}}}.}$

次に、m ₂  = 4、d ₂  = 7、a ₂  = 2です。

${\displaystyle {\frac {{\sqrt {114}}+4}{7}}=2+{\frac {{\sqrt {114}}-10}{7}}=2+{\frac {14}{7({\sqrt {114}}+10)}}=2+{\frac {1}{\frac {{\sqrt {114}}+10}{2}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+10}{2}}=10+{\frac {{\sqrt {114}}-10}{2}}=10+{\frac {14}{2({\sqrt {114}}+10)}}=10+{\frac {1}{\frac {{\sqrt {114}}+10}{7}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+10}{7}}=2+{\frac {{\sqrt {114}}-4}{7}}=2+{\frac {98}{7({\sqrt {114}}+4)}}=2+{\frac {1}{\frac {{\sqrt {114}}+4}{14}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+4}{14}}=1+{\frac {{\sqrt {114}}-10}{14}}=1+{\frac {14}{14({\sqrt {114}}+10)}}=1+{\frac {1}{\frac {{\sqrt {114}}+10}{1}}}.}$

${\displaystyle {\frac {{\sqrt {114}}+10}{1}}=20+{\frac {{\sqrt {114}}-10}{1}}=20+{\frac {14}{{\sqrt {114}}+10}}=20+{\frac {1}{\frac {{\sqrt {114}}+10}{14}}}.}$

ここで、上記の 2 番目の式に戻ります。

したがって、114の平方根の単純な連分数は

${\displaystyle {\sqrt {114}}=[10;{\overline {1,2,10,2,1,20}}].\,}$（OEISの配列A010179）

√ 114は約 10.67707 82520 です。繰り返しを 1 回展開すると、連分数は有理分数となり、その小数値は約 10.67707 80856 で、相対誤差は 0.0000016%、つまり 100,000,000 分の 1.6 になります。 ${\displaystyle {\frac {21194}{1985}}}$

より迅速な方法は、一般化された連分数を評価することです。そこから導かれる式から：

${\displaystyle {\begin{aligned}{\sqrt {z}}={\sqrt {x^{2}+y}}&=x+{\cfrac {y}{2x+{\cfrac {y}{2x+{\cfrac {y}{2x+\ddots }}}}}}\\&=x+{\cfrac {2x\cdot y}{2(2z-y)-y-{\cfrac {y^{2}}{2(2z-y)-{\cfrac {y^{2}}{2(2z-y)-\ddots }}}}}}\end{aligned}}}$

^{そして114は10 2} =100と11 ² =121 の間の2/3であるという事実は、

${\displaystyle {\begin{aligned}{\sqrt {114}}={\cfrac {\sqrt {1026}}{3}}={\cfrac {\sqrt {32^{2}+2}}{3}}&={\cfrac {32}{3}}+{\cfrac {2/3}{64+{\cfrac {2}{64+{\cfrac {2}{64+{\cfrac {2}{64+\ddots }}}}}}}}\\&={\cfrac {32}{3}}+{\cfrac {2}{192+{\cfrac {18}{192+{\cfrac {18}{192+\ddots }}}}}},\end{aligned}}}$

これは単純に前述のものを3番目の項ごとに評価したものです。分数のペアを組み合わせると、 ${\displaystyle [10;1,2,\,10,2,1,\,20,1,2]}$

${\displaystyle {\begin{aligned}{\sqrt {114}}={\cfrac {\sqrt {32^{2}+2}}{3}}&={\cfrac {32}{3}}+{\cfrac {64/3}{2050-1-{\cfrac {1}{2050-{\cfrac {1}{2050-\ddots }}}}}}\\&={\cfrac {32}{3}}+{\cfrac {64}{6150-3-{\cfrac {9}{6150-{\cfrac {9}{6150-\ddots }}}}}},\end{aligned}}}$

これは現在、第 3 学期およびその後 6 学期ごとに評価されます。 ${\displaystyle [10;1,2,{\overline {10,2,1,20,1,2}}]}$

• 連分数 – 数式
• 一般化連分数 – 数式Pages displaying short descriptions of redirect targets
• エルミートの問題
• 連分数法による平方根の計算 – 平方根を計算するアルゴリズム
• 制限された部分商 – 解析級数
• 連分数因数分解 – 整数因数分解アルゴリズムPages displaying wikidata descriptions as a fallback