自然数の平方根を任意の精度で有理数近似する方法
はじめに
この記事は 日曜数学 Advent Calendar 2020 の2日目の記事です。
ハイレベルな記事が多い(と予想される)中、私は「日曜数学」らしく趣味に走った記事を書きたいと思います。テーマに選んだのは、Twitterで数学で遊んでいたときに見つけた自然数の平方根の有理数近似の方法です。方法自体はおそらく既知のものだと思いますが、この記事では私がどうやってこの方法に思い至ったかという部分を趣味全開で記事にしたいと思います。
この記事で取り扱うのは自然数の平方根を有理数近似する方法です。
例えば、こんな近似があります。
$\sqrt{2}\fallingdotseq\frac{3363}{2378}\\ \sqrt{3}\fallingdotseq\frac{262087}{151316}\\ \sqrt{5}\fallingdotseq\frac{930249}{416020}\\ \sqrt{65537}\fallingdotseq\frac{618993631790358177581760513}{2417925426944427685841408} $
さて、上記の有理数近似はある方法で作ったものです。この方法を使うと、任意の精度で自然数の平方根を有理数近似することができます!
……「任意の精度」の表現ではよくわからないかもしれません。もう少し正確に表現してみます。自然数の平方根を次のような分数表記にしたとき、分子が「ほとんど整数」となるようなものの小数部分を四捨五入することで得られる有理数近似を「良い有理数近似」とし、分子が整数に近いものから作った近似であるほど、「より良い有理数近似」であるとしましょう。
$\sqrt{2}=\frac{3362.99985\cdots}{2378}\\ \sqrt{3}=\frac{262086.999998\cdots}{151316}\\ \sqrt{5}=\frac{930248.9999994\cdots}{416020}\\ \sqrt{65537}=\frac{618993631790358177581760512.9999999999999999999999999991\cdots}{2417925426944427685841408} $
このとき、いくらでも「より良い有理数近似」となるような分数を得る方法を見つけたということです。
その方法は、過去に私がtwitterで書いた内容と同じですし、この記事の最後に書いてありますので、結果だけ知りたい人は最後まで飛ばしてもらっても構いません。
ですが、この記事では、どのようにこの方法を思いついたかについてここから少し詳しく書いてみたいと思います。
黄金比の累乗とフィボナッチ数の関係
より良い有理数近似を作るためにまず最初に考えたのは、黄金比の累乗とフィボナッチ数の次のような関係でした。
${\displaystyle F_n=\left\lfloor\frac{\left(\frac{1+\sqrt{5}}{2}\right)^n}{\sqrt{5}}\right\rceil}$
なぜこのようなことができるのかというと、フィボナッチ数の一般項は次のように表すことができる(ビネの公式)のですが、
${\displaystyle \begin{align} F_n &= \underbrace{\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}}_{\text{第１項}} -\underbrace{\frac{\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}}_{\text{第２項}}\\ \end{align} }$
この式を観察すると、第１項は公比 $\frac{1+\sqrt{5}}{2}$ の等比数列、第２項は公比 $\frac{1-\sqrt{5}}{2}$ の等比数列となっていることがわかります。
$\left|\frac{1-\sqrt{5}}{2}\right|=0.618\cdots<1$ ですから、 $n$ が大きいときは第2項はほとんどゼロになってしまうため、四捨五入を使った表現をつくることができたのでした。
自然数の平方根の有理数近似の方法への応用
ここで「第2項がほとんどゼロになる仕組みを応用すれば、良い有理数近似を作れそう!」というヒラメキがありました。具体的には$\sqrt{n}$ と一番近い整数との差の絶対値は1未満になることを利用して次のような計算をします。
$(1-\sqrt{2})^{10}=3363-2378\sqrt{2}\\ \qquad \Rightarrow \sqrt{2}=\frac{3363-(1-\sqrt{2})^{10}}{2378}\fallingdotseq\frac{3363}{2378}$
$(2-\sqrt{3})^{10}=262087-151316\sqrt{3}\\ \qquad \Rightarrow \sqrt{3}=\frac{262087-(2-\sqrt{3})^{10}}{151316}\fallingdotseq\frac{262087}{151316}$
$(2-\sqrt{5})^{10}=930249-416020\sqrt{5}\\ \qquad \Rightarrow \sqrt{5}=\frac{932049-(2-\sqrt{5})^{10}}{416020}\fallingdotseq\frac{930249}{416020}$
$(256-\sqrt{65537})^{10}=618993631790358177581760513-2417925426944427685841408\sqrt{65537}\\ \qquad \Rightarrow \sqrt{65537}=\frac{618993631790358177581760513-(256-\sqrt{65537})^{10}}{2417925426944427685841408}\fallingdotseq\frac{618993631790358177581760513}{2417925426944427685841408}$
この方法を一般化するとこうなります。
$\lfloor \cdot \rceil$ の記号を $\lfloor x\rceil = \left\lfloor x+\frac{1}{2}\right\rfloor $ の意味で使います。以下では $k,n,A_k,B_k,N\in\mathbb{N}$ とします。$N$を次のように定めます。
${\displaystyle
N=\lfloor \sqrt{n}\rceil
}$
つまり $\sqrt{n}$ を四捨五入したものを$N$ ということです。このとき、次のようにして分数を作ります。
${\displaystyle
\left(N-\sqrt{n}\right)^{k}=A_k-B_k\sqrt{n}\\ \qquad
\Rightarrow
\sqrt{n}=\frac{A_k-\left(N-\sqrt{n}\right)^{k}}{B_k}\fallingdotseq\frac{A_k}{B_k}
}$
$A_k,B_k$ は自然数で、 $N$ の定義より$\left|N-\sqrt{n}\right|\le\frac{1}{2}$ なので
$\left|\left(N-\sqrt{n}\right)^{k}\right|\le\frac{1}{2^k}$
となり、
${\displaystyle
\sqrt{n}\fallingdotseq\frac{A_k}{B_k}
}$
であることがわかります。また、分子の誤差は $k$ を大きくすればいくらでも小さくすることができることもわかります。
任意の精度で有理数近似する式の完成
次に、$A_k,B_k$を $n,k$ の式で表すことを考えます。
$A_k,B_k$ は次の式を展開して求めましたが、
${\displaystyle
\left(N-\sqrt{n}\right)^{k}=A_k-B_k\sqrt{n}
}$…❤️
少し考えれば次のような式も成り立つことが分かります。
${\displaystyle
\left(N+\sqrt{n}\right)^{k}=A_k+B_k\sqrt{n}
}$…♠️
❤️と♠️を、$A_k,B_k$ についての連立方程式と見て解くことで次の式が得られます。
$ {\displaystyle k\in\mathbb{N},n\in\mathbb{N},A_k\in\mathbb{N},B_k\in\mathbb{N}\\ \\ \qquad\sqrt{n}\simeq\frac{A_k}{B_k}\\ }$
${\displaystyle \begin{align} \left\{ \begin{array}{l} A_k=\frac{\left(\lfloor \sqrt{n}\rceil+\sqrt{n}\right)^k+\left(\lfloor \sqrt{n}\rceil-\sqrt{n}\right)^k}{2}\\ B_k=\frac{\left(\lfloor \sqrt{n}\rceil+\sqrt{n}\right)^k-\left(\lfloor \sqrt{n}\rceil-\sqrt{n}\right)^k}{2\sqrt{n}}\\ \end{array} \right. \end{align} } $
二項係数を使うと、次のように書き換えることもできます。($A_k,B_k$の値は上記と同じものになります。)
$ {\displaystyle k\in\mathbb{N},n\in\mathbb{N},A_k\in\mathbb{N},B_k\in\mathbb{N}\\ \\ \qquad\sqrt{n}\simeq\frac{A_k}{B_k}\\ }$
${\displaystyle \begin{align} \left\{ \begin{array}{l} A_k=\sum_{i=0}^{\left\lfloor\frac{k}{2}\right\rfloor} {k \choose 2i}\lfloor \sqrt{n}\rceil^{k-2i}n^i\\ B_k=\sum_{i=0}^{\left\lfloor\frac{k-1}{2}\right\rfloor} {k \choose 2i+1}\lfloor \sqrt{n}\rceil^{k-2i-1}n^i\\ \end{array} \right. \end{align} } $
分子の誤差を $d$ とすると、誤差 $d$ は次のように評価できます。
${\displaystyle \sqrt{n}=\frac{A_k+d}{B_k}\\ |d|\le\frac{1}{2^k} }$
分母が2のべき乗になっていますので、kを大きくすればdはいくらでも小さくすることができることがわかりますね!
以上、フィボナッチ数の一般項の四捨五入表現から、自然数の平方根の良い有理数近似を得る方法を思いついたという、趣味全開の記事でした。
(追記)
もっと短い表現にできることに気が付きました。
なぜこういう表現ができるのかよかったら考えてみてください。
$ {\displaystyle k\in\mathbb{N},n\in\mathbb{N},A_k\in\mathbb{N},B_k\in\mathbb{N}\\ \\ \qquad\sqrt{n}\simeq\frac{A_k}{B_k}\\ }$
${\displaystyle \begin{align} \left\{ \begin{array}{l} A_k=\left\lfloor\frac{\left(\lfloor \sqrt{n}\rceil+\sqrt{n}\right)^k}{2}\right\rceil\\ B_k=\left\lfloor\frac{\left(\lfloor \sqrt{n}\rceil+\sqrt{n}\right)^k}{2\sqrt{n}}\right\rceil\\ \end{array} \right. \end{align} } $
この記事を高評価した人
この記事に送られたバッジ
投稿者
