ペラン数
ペラン数（英: Perrin number）とは、以下の漸化式で定義される数である。
- P(0) = 3, P(1) = 0, P(2) = 2,
- P(n) = P(n − 2) + P(n − 3) for n > 2
また、これによって得られる以下の数列をペラン数列と呼ぶ。
n-頂点の閉路グラフにおける異なる極大独立集合の個数はn番目のペラン数となる [1]。
歴史
1878年にはエドゥアール・リュカが [2] 、1899年にはR. Perrin が [3] この数列について言及している。1982年にはAdamsとShanksがこの数列について詳しく調べ、ペラン数列と名付けた[4] 。
母関数
ペラン数列の母関数は以下のようになる。
- [math]G(P(n);x)=\frac{3-x^2}{1-x^2-x^3}[/math]
行列形式
- [math] \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^n \begin{pmatrix} 2 \\ 0 \\ 3 \end{pmatrix} = \begin{pmatrix} P\left(n+2\right) \\ P\left(n+1\right) \\ P\left(n\right) \end{pmatrix} [/math]
Binetの公式
ペラン数は、以下の方程式の解の累乗を用いて表すことが出来る。
- [math] x^3 -x -1 = 0[/math]
この方程式は3つの解を持ち、1つは実数解（p とする、プラスチック数と呼ばれる）、2つは複素共役な解（q, r とする）である。これらを用いて、フィボナッチ数列におけるBinetの公式と同様の公式を得ることが出来る。
- [math]P\left(n\right) = {p^n} + {q^n} + {r^n} [/math]
複素解 q, r の絶対値は1より小さいので、 n を大きくすれば q^n, r^n は0に近づく。従って、十分大きな n に対しては、公式は以下のように簡略化出来る。
- [math]P\left(n\right) \approx {p^n} [/math]
この公式は、大きな n に対してペラン数を高速に計算するのに用いられる。ペラン数列の連続する項の比は p 、つまりプラスチック数に近づき、その値はおおよそ 1.324718 である。ペラン数列・パドヴァン数列におけるプラスチック数は、フィボナッチ数列における黄金比や、ペル数における白銀比に対応するものとなっている。
乗法公式
Binetの公式を用いて、 G(kn) を G(n−1), G(n) , G(n+1) で表すことが出来る。
- [math] \begin{matrix} G(n-1) & = &p^{-1}p^n + &q^{-1}q^n +& r^{-1} r^n\\ G(n) & =& p^n+&q^n+&r^n\\ G(n+1) &=& pp^n +& qq^n +& rr^n\end{matrix}[/math]
であるが、これは [math] x^3 -x -1[/math] の分解体上の係数を持つ3つの線型方程式であり、逆行列を求めることで[math]p^n, q^n, r^n[/math]を計算することが出来る。これらを k 乗し、和を求めればよい。
magmaでのコードの例を以下に示す。
P<x> := PolynomialRing(Rationals()); S<t> := SplittingField(x^3-x-1); P2<y> := PolynomialRing(S); p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]); Mi:=Matrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1); T<u,v,w> := PolynomialRing(S,3); v1 := ChangeRing(Mi,T) *Matrix([[u],[v],[w]]); [p^i*v1[1,1]^3 + q^i*v1[2,1]^3 + r^i*v1[3,1]^3 : i in [-1..1]];
[math]u = G(n-1), v = G(n), w = G(n+1)[/math]とすれば
- [math] \begin{matrix} 23G(2n-1) &=& 4u^2 + 3v^2 + 9w^2 + 18uv - 12uw - 4vw \\ 23G(2n) &=& 18uw - 4uv + 6vw - 6u^2 + 7v^2 - 2w^2\\ 23G(2n+1) &=& 9u^2 + v^2 + 3w^2 + 6uv - 4uw - 14vw \\ 23G(3n-1)& = &\left(-4u^3 + 2v^3 -w^3 + 9(uv^2+vw^2+wu^2) + 3v^2w+6uvw\right)\\ 23G(3n)& = &\left(3u^3 + 2v^3 + 3w^3 - 3(uv^2 + uw^2 + vw^2 + vu^2) + 6v^2w + 18uvw\right) \\ 23G(3n+1)& = &\left(v^3-w^3+6uv^2+9uw^2+6vw^2+9vu^2-3wu^2+6wv^2-6uvw\right) \end{matrix} [/math]
となる。23という数字は定義多項式の判別式に由来する。
これを用いれば、整数演算によってn番目のペラン数を [math]O(\log n)[/math] 回の乗算で求めることが出来る。
素数、整除性
P(n) が n で割り切れるような n を列挙すると以下のようになる。
- n = 1, 2, 3, 5, 7, 11, 13, ...
1の後にはしばらく素数が続いている。全ての素数 p に対して、 P(p) が p で割り切れることが証明されている。しかし、その逆は成り立たない。すなわち、P(n) が n で割り切れるような合成数 n が存在する。このような n をペラン擬素数（Perrin pseudoprime）と呼ぶ。「ペラン擬素数は存在するか」という疑問はPerrin自身も考察しており、後にAdamsとShanksが最小のペラン擬素数 271441 = 5212 を発見し[4]肯定的に解決された。2番目に小さいペラン擬素数は 904631 = 7 x 13 x 9941 である。10億未満のペラン擬素数は17個存在する[5]。また、無限に多くのペラン擬素数が存在することがJon Granthamによって証明されている[6]。
素数であるペラン数をペラン素数（Perrin prime）と呼ぶ（オンライン整数列大辞典の数列 A074788）。
- 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797
2006年5月にE. W. Weissteinが発見した32,147桁のペラン数 P(263226) はおそらくペラン素数であろうと考えられている。
注釈、参考文献
- ↑ *Füredi, Z. (1987). “The number of maximal independent sets in connected graphs”. Journal of Graph Theory 11 (4): 463–470. doi:10.1002/jgt.3190110403.
- ↑ *Lucas, E. (1878). “Théorie des fonctions numériques simplement périodiques”. American Journal of Mathematics 1: 197–240. doi:10.2307/2369311.
- ↑ *Perrin, R. (1899). “Query 1484”. L'Intermediaire Des Mathematiciens 6: 76.
- ↑ 4.0 4.1 *Adams, William; Shanks, Daniel (1982). “Strong primality tests that are not sufficient”. Mathematics of Computation 39 (159): 255–300. doi:10.2307/2007637. MR0658231.
- ↑ オンライン整数列大辞典の数列 A013998
- ↑ There are infinitely many Perrin pseudoprimes, Jon Grantham, Journal of Number Theory (2010).