初等整数論 [5]
●フィボナッチ数列
数学では、次の漸化式で生成される数列を「フィボナッチ数列」といいます。
\(\begin{cases}
F_0 = 0 & \\
F_1 = 1 & \\
F_n = F_{n - 1} + F_{n - 2} & \mathrm{if} \ n \gt 1
\end{cases}\)
フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13, .... という直前の 2 項を足していく数列になります。
参考文献 1 によると、フィボナッチ数の一般項は次の式で与えられるそうです。
\(
F_n = \dfrac{1}{\sqrt 5} \left\{\left(\dfrac{1 + \sqrt 5}{2}\right)^n - \left(\dfrac{1 - \sqrt 5}{2}\right)^n\right\}
\)
これを「ピネの公式」といいます。
[証明]
漸化式を行列で表すと以下の式になる
\(\begin{pmatrix}
F_{n+2} \\
F_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_{n+1} \\
F_n
\end{pmatrix}\)
上式は帰納的に次式のようになる
\(\begin{pmatrix}
F_{n+1} \\
F_n
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}^n
\begin{pmatrix}
F_1 \\
F_0
\end{pmatrix}\)
\(A =
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}\) の固有値を \(\alpha, \beta\) とし、\(B = \begin{pmatrix}
\alpha & 0 \\
0 & \beta
\end{pmatrix}\)
とする
\(A = P B P^{-1}\) を満たす行列 \(P\) が存在するならば、次式が成り立つ
\(\begin{eqnarray}
A^n &=& \left(P B P^{-1}\right)^n = \left(P B P^{-1} \right) \left(P B P^{-1}\right) \left(P B P^{-1} \right) \cdots \left(P B P^{-1}\right)\left(P B P^{-1}\right)\left(P B P^{-1}\right) \\
&=& P B^n P^{-1} \\
&=& P
\begin{pmatrix}
\alpha^n & 0 \\
0 & \beta^n
\end{pmatrix}
P^{-1}
\end{eqnarray}\)
\(P\) は \(A\) の固有ベクトルから求めることができる
[固有値]
\(
\left| A - \lambda I \right| =
\begin{vmatrix}
1 - \lambda & 1 \\
1 & - \lambda
\end{vmatrix}
= \lambda^2 - \lambda - 1 = 0 \quad \therefore \lambda = \dfrac{1 \pm \sqrt 5}{2}
\)
\(\alpha = \dfrac{1 + \sqrt 5}{2}, \ \beta = \dfrac{1 - \sqrt 5}{2} \) とする
[固有ベクトル]
\(
x_i = \begin{pmatrix}
a \\
b
\end{pmatrix}\)
とすると、
\(\left(A - \lambda I\right) x_i = O\) より、
\(\begin{pmatrix}
1 - \lambda & 1 \\
1 & - \lambda
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
= \begin{pmatrix}
(1 - \lambda)a + b \\
a - \lambda b
\end{pmatrix}
= O \quad \therefore a = \lambda b
\)
\(b = 1\) とすると、固有ベクトルは \(x_1 = \begin{pmatrix}
\alpha \\
1
\end{pmatrix}
, x_2 = \begin{pmatrix}
\beta \\
1
\end{pmatrix}
\) だから、\(P = (x_1, x_2) =
\begin{pmatrix}
\alpha & \beta \\
1 & 1
\end{pmatrix}\)
になる
[公式の導出]
\(
\begin{pmatrix}
F_{n+1} \\
F_n
\end{pmatrix}
= \begin{pmatrix}
\alpha & \beta \\
1 & 1
\end{pmatrix}
\begin{pmatrix}
\alpha^n & 0 \\
0 & \beta^n
\end{pmatrix}
\dfrac{1}{\alpha - \beta}
\begin{pmatrix}
1 & -\beta \\
-1 & \alpha
\end{pmatrix}
\begin{pmatrix}
1 \\
0
\end{pmatrix}
\)
\(
\begin{pmatrix}
F_{n+1} \\
F_n
\end{pmatrix}
= \dfrac{1}{\sqrt 5}\begin{pmatrix}
\alpha^{n+1} - \beta^{n+1} & -\beta\alpha^{n+1} + \alpha\beta^{n+1} \\
\alpha^n - \beta^n & -\beta\alpha^n + \alpha\beta^n
\end{pmatrix}
\begin{pmatrix}
1 \\
0
\end{pmatrix}\)
\(
\therefore F_n = \dfrac{1}{\sqrt 5} \left\{\left(\dfrac{1 + \sqrt 5}{2}\right)^n - \left(\dfrac{1 - \sqrt 5}{2}\right)^n\right\} = \dfrac{\phi^n + (1 - \phi)^n}{\sqrt 5} = \dfrac{\phi^n - (- \phi)^{-n}}{\sqrt 5}
\)
[補足]
二次方程式 \(ax^2 + bx + c = 0\) の解を \(\alpha, \beta\) とすると、\(\alpha + \beta = -\frac{b}{a}, \ \alpha\beta = \frac{c}{a}\) が成り立つ
\(x^2 - x - 1 = 0\) の場合、\(a = 1, b = -1, c = -1\) なので
\(\beta = 1 - \alpha = 1 - \phi, \beta = -\frac{1}{\alpha} = (-\phi)^{-1}\) が成り立つ
\(\phi = \frac{1 + \sqrt 5}{2} \) を「黄金数」とか「黄金分割比」といいます。Python で計算すると、値は次のようになります。
>>> phi = (1 + math.sqrt(5)) / 2
>>> phi
1.618033988749895
フィボナッチ数列の隣り合う二項の比は黄金数に収束します。
[証明]
\(|1 - \phi| \lt 1\) だから \(\lim_{n \to \infty} (1 - \phi)^n\) は \(0\) に収束する。よって、
\(
\displaystyle \lim_{n \to \infty} \dfrac{F_{n+1}}{F_n} = \lim_{n \to \infty} \dfrac{\phi^{n+1} - (1 - \phi)^{n+1}}{\phi^n - (1 - \phi)^n} = \phi
\)
\(\phi\) を連分数展開すると、次のようになります。
\(
\phi = 1 + \dfrac{1}{1 + \dfrac{1}{1 + \dfrac{1}{1 + \frac{1}{\cdots}}}} = [1; 1, 1, 1, \ldots]
\)
連分数で \(\phi\) の有理数近似を順番に求めると、分子と分母はフィボナッチ数列になります。
>>> import sympy as sy
>>> for n in range(1, 21): print(sy.continued_fraction_reduce([1 for _ in range(n)]))
...
1
2
3/2
5/3
8/5
13/8
21/13
34/21
55/34
89/55
144/89
233/144
377/233
610/377
987/610
1597/987
2584/1597
4181/2584
6765/4181
10946/6765
公式の後半 \(\frac{1}{\sqrt 5} \left(\frac{1 - \sqrt 5}{2}\right)^n\) の絶対値は 0.5 未満になるとのことなので、フィボナッチ数は次の式で求めることができます。
\(
F_n = \left \lfloor \dfrac{1}{\sqrt 5} \left( \dfrac{1 + \sqrt 5}{2} \right)^n + 0.5 \right \rfloor
\)
\(
F_n = \left \lfloor \dfrac{\phi^n}{\sqrt 5} + 0.5 \right \rfloor
\)
SymPy にはフィボナッチ数 \(F_n\) を求める関数 fibonacci(n) があります。簡単な実行例を示します。
>>> for n in range(21): print(sy.fibonacci(n), end=" ")
...
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
>>> for n in range(21): print(math.floor((phi ** n)/math.sqrt(5) + 0.5), end=" ")
...
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
>>> for n in range(41, 46): print(sy.fibonacci(n), end=" ")
...
165580141 267914296 433494437 701408733 1134903170 >>>
>>> for n in range(41, 46): print(math.floor((phi ** n)/math.sqrt(5) + 0.5), end=" ")
...
165580141 267914296 433494437 701408733 1134903170
●リュカ数
次の漸化式で生成される数列の項を「リュカ数 (Lucas number)」といいます。
\(\begin{cases}
L_0 = 2 & \\
L_1 = 1 & \\
L_n = L_{n-1} + L_{n-2} & \mathrm{if} \ n \gt 1
\end{cases}\)
フィボナッチ数列の最初の 2 項を 2, 1 に置き換えただけで、2, 1, 3, 4, 7, 11, 18, 29, 47, ... という数列になります。一般項は次のようになります。
\(
L_n = \left(\dfrac{1 + \sqrt 5}{2}\right)^n + \left(\dfrac{1 - \sqrt 5}{2}\right)^n = \phi^n + (1 - \phi)^n = \phi^n + (-\phi)^{-n}
\)
[証明]
\(
\begin{pmatrix}
L_{n+1} \\
L_n
\end{pmatrix}
= \dfrac{1}{\sqrt 5}\begin{pmatrix}
\alpha^{n+1} - \beta^{n+1} & -\beta\alpha^{n+1} + \alpha\beta^{n+1} \\
\alpha^n - \beta^n & -\beta\alpha^n + \alpha\beta^n
\end{pmatrix}
\begin{pmatrix}
1 \\
2
\end{pmatrix}\)
\(\begin{eqnarray}
L_n &=& \dfrac{1}{\sqrt 5}\left( \alpha^n - \beta^n + 2\left(-\beta\alpha^n + \alpha\beta^n\right) \right) \\
&=& \dfrac{1}{\sqrt 5}\left( (1 - 2\beta)\alpha^n - (1 - 2\alpha)\beta^n \right) \\
&=& \dfrac{1}{\sqrt 5}\left( (\sqrt 5)\alpha^n - (- \sqrt 5)\beta^n \right) \\
&=& \alpha^n + \beta^n = \left(\dfrac{1 + \sqrt 5}{2}\right)^n + \left(\dfrac{1 - \sqrt 5}{2}\right)^n
\end{eqnarray}\)
SymPy にはリュカ数を求める関数 lucas(n) が用意されています。簡単な実行例を示します。
>>> for i in range(40): print(sy.lucas(i), end=" ")
...
2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127 24476 39603 64079
103682 167761 271443 439204 710647 1149851 1860498 3010349 4870847 7881196 12752043 20633239
33385282 54018521 87403803 141422324
●ペル数
ペル数 (Pell number) は、以下の漸化式で生成される数列の各項のことです。
\(\begin{cases}
P_1 = 1 & \\
P_2 = 2 & \\
P_n = 2 \times P_{n-1} + P_{n-2} & \mathrm{if} \ n \geqq 3
\end{cases}\)
ペル数は 1, 2, 5, 12, 29, 70, 169, 408, 985, ... という数列になります。
参考 URL 6 によると、ペル数の一般項は次の式で与えられるそうです。
\(
P_n = \dfrac{\left(1 + \sqrt 2\right)^n - \left(1 - \sqrt 2\right)^n}{2 \sqrt 2}
\)
[証明]
漸化式を行列で表すと以下の式になる
\(\begin{pmatrix}
P_{n+2} \\
P_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
2 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
P_{n+1} \\
P_n
\end{pmatrix}\)
上式は帰納的に次式のようになる
\(\begin{pmatrix}
P_{n+2} \\
P_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
2 & 1 \\
1 & 0
\end{pmatrix}^n
\begin{pmatrix}
P_2 \\
P_1
\end{pmatrix}\)
\(A =
\begin{pmatrix}
2 & 1 \\
1 & 0
\end{pmatrix}\) の固有値を \(\alpha, \beta\) とし、\(B = \begin{pmatrix}
\alpha & 0 \\
0 & \beta
\end{pmatrix}\)
とする
\(A = P B P^{-1}\) を満たす行列 \(P\) が存在するならば、次式が成り立つ
\(\begin{eqnarray}
A^n &=& \left(P B P^{-1}\right)^n = \left(P B P^{-1} \right) \left(P B P^{-1}\right) \left(P B P^{-1} \right) \cdots \left(P B P^{-1}\right)\left(P B P^{-1}\right)\left(P B P^{-1}\right) \\
&=& P B^n P^{-1} \\
&=& P
\begin{pmatrix}
\alpha^n & 0 \\
0 & \beta^n
\end{pmatrix}
P^{-1}
\end{eqnarray}\)
\(P\) は \(A\) の固有ベクトルから求めることができる
[固有値]
\(
\left| A - \lambda I \right| =
\begin{vmatrix}
2 - \lambda & 1 \\
1 & - \lambda
\end{vmatrix}
= \lambda^2 - 2 \lambda - 1 = 0 \quad \therefore \lambda = 1 \pm \sqrt 2
\)
\(\alpha = 1 + \sqrt 2, \ \beta = 1 - \sqrt 2\) とする
[固有ベクトル]
\(
x_i = \begin{pmatrix}
a \\
b
\end{pmatrix}\)
とすると、
\(\left(A - \lambda I\right) x_i = O\) より、
\(\begin{pmatrix}
2 - \lambda & 1 \\
1 & - \lambda
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
= \begin{pmatrix}
(2 - \lambda)a + b \\
a - \lambda b
\end{pmatrix}
= O \quad \therefore a = \lambda b
\)
\(b = 1\) とすると、固有ベクトルは \(x_1 = \begin{pmatrix}
\alpha \\
1
\end{pmatrix}
, x_2 = \begin{pmatrix}
\beta \\
1
\end{pmatrix}
\) だから、\(P = (x_1, x_2) =
\begin{pmatrix}
\alpha & \beta \\
1 & 1
\end{pmatrix}\)
になる
[公式の導出]
\(\begin{eqnarray}
\begin{pmatrix}
P_{n+2} \\
P_{n+1}
\end{pmatrix}
&=& \begin{pmatrix}
\alpha & \beta \\
1 & 1
\end{pmatrix}
\begin{pmatrix}
\alpha^n & 0 \\
0 & \beta^n
\end{pmatrix}
\dfrac{1}{\alpha - \beta}
\begin{pmatrix}
1 & -\beta \\
-1 & \alpha
\end{pmatrix}
\begin{pmatrix}
2 \\
1
\end{pmatrix} \\
&=& \dfrac{1}{2 \sqrt 2}\begin{pmatrix}
\alpha^{n+1} - \beta^{n+1} & -\beta\alpha^{n+1} + \alpha\beta^{n+1} \\
\alpha^n - \beta^n & -\beta\alpha^n + \alpha\beta^n
\end{pmatrix}
\begin{pmatrix}
2 \\
1
\end{pmatrix} \\
&=& \dfrac{1}{2 \sqrt 2}\begin{pmatrix}
2 \left(\alpha^{n+1} - \beta^{n+1}\right) - \beta\alpha^{n+1} + \alpha\beta^{n+1} \\
2 \left(\alpha^n - \beta^n\right) - \beta\alpha^n + \alpha\beta^n
\end{pmatrix} \\
&=& \dfrac{1}{2 \sqrt 2}\begin{pmatrix}
(2 - \beta)\alpha^{n+1} - (2 - \alpha) \beta^{n+1} \\
(2 - \beta)\alpha^n - (2 - \alpha) \beta^n
\end{pmatrix}
\end{eqnarray}
\)
\(2 - \alpha = \beta, 2 - \beta = \alpha\) より
\(
\begin{pmatrix}
P_{n+2} \\
P_{n+1}
\end{pmatrix}
=
\dfrac{1}{2 \sqrt 2}\begin{pmatrix}
\alpha^{n+2} - \beta^{n+2} \\
\alpha^{n+1} - \beta^{n+1}
\end{pmatrix}
\quad
\therefore P_n = \dfrac{\left(1 + \sqrt 2\right)^n - \left(1 - \sqrt 2\right)^n}{2 \sqrt 2}
\)
\( 1 + \sqrt 2 \) を「白銀数」といい、\(1 : 1 + \sqrt 2\) を「白銀比」といいます。Python で計算すると、値は次のようになります。
>>> 1 + math.sqrt(2)
2.414213562373095
ペル数の隣り合う二項の比は白銀数に収束します。Python でプログラムを作って確かめてみましょう。
リスト : ペル数
def pell_number(n):
a, b = 1, 0
while n > 1:
c = a
a = 2 * a + b
b = c
n -= 1
return a
>>> for n in range(1, 11): print(pell_number(n))
...
1
2
5
12
29
70
169
408
985
2378
>>> for n in range(1, 11): print(pell_number(n + 1) / pell_number(n))
...
2.0
2.5
2.4
2.4166666666666665
2.413793103448276
2.414285714285714
2.4142011834319526
2.4142156862745097
2.414213197969543
2.41421362489487
[証明]
\(|1 - \sqrt 2| \lt 1\) だから \(\lim_{n \to \infty} (1 - \sqrt 2)^n\) は \(0\) に収束する。よって、
\(
\displaystyle \lim_{n \to \infty} \dfrac{P_{n+1}}{P_n} = \lim_{n \to \infty} \dfrac{\alpha^{n+1} - \beta^{n+1}}{\alpha^n - \beta^n} = \alpha = 1 + \sqrt 2
\)
白銀数を連分数展開すると、次のようになります。
\(
1 + \sqrt 2 = 2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \frac{1}{\cdots}}}} = [2; 2, 2, 2, \ldots]
\)
連分数で白銀数の有理数近似を順番に求めると、分子と分母はペル数になります。
>>> import sympy as sy
>>> for n in range(1, 21): print(sy.continued_fraction_reduce([2 for _ in range(n)]))
...
2
5/2
12/5
29/12
70/29
169/70
408/169
985/408
2378/985
5741/2378
13860/5741
33461/13860
80782/33461
195025/80782
470832/195025
1136689/470832
2744210/1136689
6625109/2744210
15994428/6625109
38613965/15994428
●貴金属数
数学では、次の数を「貴金属数 (metallic number)」といいます。
\(
\dfrac{n + \sqrt {n^2 + 4}}{2}
\)
n = 1 が黄金数、n = 2 が白銀数になります。そして、n = 3 を青銅数といい、n 番目の貴金属数を第 n 貴金属数といいます。次の漸化式で生成する数列において、隣り合う二項の比は第 n 貴金属数に収束します。
\(
\begin{cases}
M_0 = 0 & \\
M_1 = 1 & \\
M_{k+2} = n M_{k+1} + M_k & \mathrm{if} \ k \gt 0
\end{cases}
\)
Python でプログラムを作って確かめてみましょう。
リスト : 貴金属数
def metallic(n, k):
a, b = 0, 1
while k > 0:
c = a
a = n * a + b
b = c
k -= 1
return a
>>> for n in range(1, 10):
... print(n, " : ", end=" ")
... for k in range(0, 11): print(metallic(n, k), end=" ")
... print("")
...
1 : 0 1 1 2 3 5 8 13 21 34 55
2 : 0 1 2 5 12 29 70 169 408 985 2378
3 : 0 1 3 10 33 109 360 1189 3927 12970 42837
4 : 0 1 4 17 72 305 1292 5473 23184 98209 416020
5 : 0 1 5 26 135 701 3640 18901 98145 509626 2646275
6 : 0 1 6 37 228 1405 8658 53353 328776 2026009 12484830
7 : 0 1 7 50 357 2549 18200 129949 927843 6624850 47301793
8 : 0 1 8 65 528 4289 34840 283009 2298912 18674305 151693352
9 : 0 1 9 82 747 6805 61992 564733 5144589 46866034 426938895
>>> for k in range(1, 10): print(metallic(1, k + 1) / metallic(1, k))
...
1.0
2.0
1.5
1.6666666666666667
1.6
1.625
1.6153846153846154
1.619047619047619
1.6176470588235294
>>> for k in range(1, 10): print(metallic(2, k + 1) / metallic(2, k))
...
2.0
2.5
2.4
2.4166666666666665
2.413793103448276
2.414285714285714
2.4142011834319526
2.4142156862745097
2.414213197969543
>>> for k in range(1, 10): print(metallic(3, k + 1) / metallic(3, k))
...
3.0
3.3333333333333335
3.3
3.303030303030303
3.302752293577982
3.3027777777777776
3.302775441547519
3.3027756557168324
3.302775636083269
>>> for k in range(1, 10): print(metallic(8, k + 1) / metallic(8, k))
...
8.0
8.125
8.123076923076923
8.12310606060606
8.123105619025415
8.123105625717566
8.123105625616146
8.123105625617683
8.12310562561766
貴金属数を連分数展開すると、次のようになります。
\(
\dfrac{n + \sqrt {n^2 + 4}}{2} = n + \dfrac{1}{n + \dfrac{1}{n + \dfrac{1}{n + \frac{1}{\cdots}}}} = [n; n, n, n, \ldots]
\)
連分数で貴金属数の有理数近似を順番に求めると、上記で示した漸化式で生成される数が分子と分母に並びます。
>>> import sympy as sy
>>> for n in range(1, 21): print(sy.continued_fraction_reduce([3 for _ in range(n)]))
...
3
10/3
33/10
109/33
360/109
1189/360
3927/1189
12970/3927
42837/12970
141481/42837
467280/141481
1543321/467280
5097243/1543321
16835050/5097243
55602393/16835050
183642229/55602393
606529080/183642229
2003229469/606529080
6616217487/2003229469
21851881930/6616217487
>>> for n in range(1, 21): print(sy.continued_fraction_reduce([8 for _ in range(n)]))
...
8
65/8
528/65
4289/528
34840/4289
283009/34840
2298912/283009
18674305/2298912
151693352/18674305
1232221121/151693352
10009462320/1232221121
81307919681/10009462320
660472819768/81307919681
5365090477825/660472819768
43581196642368/5365090477825
354014663616769/43581196642368
2875698505576520/354014663616769
23359602708228929/2875698505576520
189752520171407952/23359602708228929
1541379764079492545/189752520171407952
一般項はフィボナッチ数列やペル数と同様に求めることができます。
\(\begin{pmatrix}
M_{k+1} \\
M_k
\end{pmatrix}
=
\begin{pmatrix}
n & 1 \\
1 & 0
\end{pmatrix}^k
\begin{pmatrix}
M_1 \\
M_0
\end{pmatrix}\)
行列 \(A =
\begin{pmatrix}
n & 1 \\
1 & 0
\end{pmatrix}\) の固有値と固有ベクトルを求める
[固有値]
\(
\left| A - \lambda I \right| =
\begin{vmatrix}
n - \lambda & 1 \\
1 & - \lambda
\end{vmatrix}
= \lambda^2 - n \lambda - 1 = 0 \quad \therefore \lambda = \dfrac{n \pm \sqrt {n^2 + 4}}{2}
\)
\(\alpha = \dfrac{n + \sqrt {n^2 + 4}}{2}, \ \beta = \dfrac{n - \sqrt {n^2 + 4}}{2} \) とする
[固有ベクトル]
\(
x_i = \begin{pmatrix}
a \\
b
\end{pmatrix}\)
とすると、
\(\left(A - \lambda I\right) x_i = O\) より、
\(\begin{pmatrix}
n - \lambda & 1 \\
1 & - \lambda
\end{pmatrix}
\begin{pmatrix}
a \\
b
\end{pmatrix}
= \begin{pmatrix}
(n - \lambda)a + b \\
a - \lambda b
\end{pmatrix}
= O \quad \therefore a = \lambda b
\)
\(b = 1\) とすると、固有ベクトルは \(x_1 = \begin{pmatrix}
\alpha \\
1
\end{pmatrix}
, x_2 = \begin{pmatrix}
\beta \\
1
\end{pmatrix}
\) だから、\(P = (x_1, x_2) =
\begin{pmatrix}
\alpha & \beta \\
1 & 1
\end{pmatrix}\)
になる
[公式の導出]
\(
\begin{pmatrix}
M_{k+1} \\
M_k
\end{pmatrix}
= \begin{pmatrix}
\alpha & \beta \\
1 & 1
\end{pmatrix}
\begin{pmatrix}
\alpha^k & 0 \\
0 & \beta^k
\end{pmatrix}
\dfrac{1}{\alpha - \beta}
\begin{pmatrix}
1 & -\beta \\
-1 & \alpha
\end{pmatrix}
\begin{pmatrix}
1 \\
0
\end{pmatrix}
\)
\(
\begin{pmatrix}
M_{k+1} \\
M_n
\end{pmatrix}
= \dfrac{1}{\sqrt {n^2 + 4}}\begin{pmatrix}
\alpha^{k+1} - \beta^{k+1} & -\beta\alpha^{k+1} + \alpha\beta^{k+1} \\
\alpha^k - \beta^k & -\beta\alpha^k + \alpha\beta^k
\end{pmatrix}
\begin{pmatrix}
1 \\
0
\end{pmatrix}\)
\(
\therefore M_k = \dfrac{1}{\sqrt {n^2 + 4}} \left( \left(\dfrac{n + \sqrt {n^2 + 4}}{2}\right)^k - \left(\dfrac{n - \sqrt {n^2 + 4}}{2}\right)^k\right) = \dfrac{\mu^k - (-\mu)^{-k}}{\sqrt {n^2 + 4}}
\)
[補足]
第 n 貴金属数を \(\mu = \alpha\) とすると、\(\alpha\beta = \frac{-1}{1}\) より \(\beta = (- \mu)^{-1}\) となる
●ペル方程式
変数の個数が式の本数よりも多い方程式を「不定方程式」といいます。一次不定方程式 \(ax + by = c \ (c \ne 0)\) は、\(a, b, c\) が整数で、\(c\) が \(a\) と \(b\) の最大公約数の倍数であるとき、整数解を持つことが知られています。これを「ベズーの等式」といいます。二次の不定方程式では、以下に示す「ペル方程式 (Pell's Equation)」が有名です。
\(
x^2 - m y^2 = 1
\)
\(m\) が平方数でない正の整数とき、ペル方程式は自明の解 (\(x = 1, y = 0\)) 以外の整数解を無限個持つことが知られています。その中で \(x + y\sqrt m\) を最小にする解を \(x_1, y_1\) とすると、ペル方程式の解は次式で表すことができます。
\(
x_n + y_n \sqrt m = \left(x_1 + y_1 \sqrt m\right)^n
\)
ただし、\(n\) は正の整数
ペル方程式の解はこれで全部です。最小解 \(x_1, y_1\) は \(\sqrt m\) の連分数展開で求めることができます。
\(\sqrt m\) の 1 周期分の連分数展開を \([a_0; a_1, a_2, \ldots, a_{k-1}, a_k]\) とする
その有理数近似 \([a_0; a_1, a_2, \ldots, a_{k-1}] =\frac{p}{q}\) は次式を満たす最小解になる
\(
p^2 -mq^2 = \pm1
\)
右辺が -1 になる場合は \(p + q\sqrt m\) の二乗を計算する
\(\begin{array}{l}
x + y\sqrt m = \left(p + q\sqrt m\right)^2 = p^2 + mq^2 + 2pq\sqrt m \\
x = p^2 + mq^2 \\
y = 2pq
\end{array}\)
簡単な例を示しましょう。
\(\begin{array}{l}
\sqrt 2 = [1; 2], [1] = \dfrac{1}{1} \\
1^2 - 2 \times 1^2 = -1 \\
x = 1^2 + 2 \times 1^2 = 3 \\
y = 2 \times 1 \times 1 = 2 \\
3^2 - 2 \times 2^2 = 1
\end{array}\)
\(\begin{array}{l}
\sqrt 3 = [1; 1, 2], [1; 1] = \dfrac{2}{1} \\
2^2 - 3 \times 1^2 = 1 \\
x = 2 \\
y = 1
\end{array}\)
\(\begin{array}{l}
\sqrt 7 = [2; 1, 1, 1, 4], [2; 1, 1, 1] = \dfrac{8}{3} \\
8^2 - 7 \times 3^2 = 64 - 63 = 1 \\
x = 8 \\
y = 3
\end{array}\)
\(\begin{array}{l}
\sqrt 13 = [3; 1, 1, 1, 1, 6], [3; 1, 1, 1, 1] = \dfrac{18}{5} \\
18^2 - 13 \times 5^2 = 324 - 325 = -1 \\
x = 18^2 + 13 \times 5^2 = 649 \\
y = 13 \times 18 \times 5 = 180 \\
649^2 - 13 \times 180^2 = 421201 - 421200 = 1
\end{array}\)
循環節の長さが偶数の場合、\(x^2 - m y^2\) は \(+1\) になり、奇数の場合は \(-1\) になります。
プログラミングに興味のある方は、拙作のページをお読みくださいませ。
- Algorithms with Python: 分数
- Common Lisp 入門: 分数 [2]
●参考文献・URL
- 奥村晴彦,『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
- 平方根の連分数とペル方程式 (PDF), (有澤健治さん)
- ペル方程式に関する基本的な性質まとめ, (マスオさん)
- フィボナッチ数 - Wikipedia
- ペル方程式 - Wikipedia
- ペル数 - Wikipedia
- 貴金属比 - Wikipedia