ペラン数

ペラン数（英: Perrin number）とは、以下の漸化式で定義される数である。 P ( 0 ) = 3 , P ( 1 ) = 0 , P ( 2 ) = 2 , P ( n ) = P ( n − 2 ) + P ( n − 3 ) n > 2 {\displaystyle {\begin{aligned}&P(0)=3,P(1)=0,P(2)=2,\\&P(n)=P(n-2)+P(n-3)n>2\end{aligned}}} また、これによって得られる以下の数列をペラン数列と呼ぶ。 3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... （オンライン整数列大辞典の数列 A001608） n-頂点の閉路グラフにおける異なる極大独立集合の個数はn番目のペラン数となる 。 1878年にはエドゥアール・リュカが 、1899年にはR. Perrin が この数列について言及している。1982年にはAdamsとShanksがこの数列について詳しく調べ、ペラン数列と名付けた 。 ペラン数列の母関数は以下のようになる。 G ( P ( n ) ; x ) = 3 − x 2 1 − x 2 − x 3 {\displaystyle G(P(n);x)={\frac {3-x^{2}}{1-x^{2}-x^{3}}}} ( 0 1 1 1 0 0 0 1 0 ) n ( 2 0 3 ) = ( P ( n + 2 ) P ( n + 1 ) P ( n ) ) {\displaystyle {\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}}} ペラン数は、以下の方程式の解の累乗を用いて表すことが出来る。 x 3 − x − 1 = 0 {\displaystyle x^{3}-x-1=0} この方程式は3つの解を持ち、1つは実数解（p とする、プラスチック数と呼ばれる）、2つは複素共役な解（q, r とする）である。これらを用いて、フィボナッチ数列におけるBinetの公式と同様の公式を得ることが出来る。 P ( n ) = p n + q n + r n {\displaystyle P\left(n\right)={p^{n}}+{q^{n}}+{r^{n}}} 複素解 q, r の絶対値は1より小さいので、 n を大きくすれば q^n, r^n は0に近づく。従って、十分大きな n に対しては、公式は以下のように簡略化出来る。 P ( n ) ≈ p n {\displaystyle P\left(n\right)\approx {p^{n}}} この公式は、大きな n に対してペラン数を高速に計算するのに用いられる。ペラン数列の連続する項の比は p 、つまりプラスチック数に近づき、その値はおおよそ 1.324718 である。ペラン数列・パドヴァン数列におけるプラスチック数は、フィボナッチ数列における黄金比や、ペル数における白銀比に対応するものとなっている。 Binetの公式を用いて、 G(kn) を G(n−1), G(n) , G(n+1) で表すことが出来る。 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 ) = p p n + q q n + r r n {\displaystyle {\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}}} であるが、これは x 3 − x − 1 {\displaystyle x^{3}-x-1} の分解体上の係数を持つ3つの線型方程式であり、逆行列を求めることで p n , q n , r n {\displaystyle p^{n},q^{n},r^{n}} を計算することが出来る。これらを 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]]; u = G ( n − 1 ) , v = G ( n ) , w = G ( n + 1 ) {\displaystyle u=G(n-1),v=G(n),w=G(n+1)} とすれば 23 G ( 2 n − 1 ) = 4 u 2 + 3 v 2 + 9 w 2 + 18 u v − 12 u w − 4 v w 23 G ( 2 n ) = 18 u w − 4 u v + 6 v w − 6 u 2 + 7 v 2 − 2 w 2 23 G ( 2 n + 1 ) = 9 u 2 + v 2 + 3 w 2 + 6 u v − 4 u w − 14 v w 23 G ( 3 n − 1 ) = ( − 4 u 3 + 2 v 3 − w 3 + 9 ( u v 2 + v w 2 + w u 2 ) + 3 v 2 w + 6 u v w ) 23 G ( 3 n ) = ( 3 u 3 + 2 v 3 + 3 w 3 − 3 ( u v 2 + u w 2 + v w 2 + v u 2 ) + 6 v 2 w + 18 u v w ) 23 G ( 3 n + 1 ) = ( v 3 − w 3 + 6 u v 2 + 9 u w 2 + 6 v w 2 + 9 v u 2 − 3 w u 2 + 6 w v 2 − 6 u v w ) {\displaystyle {\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^{2}w+6uvw\right)\\23G(3n)&=&\left(3u^{3}+2v^{3}+3w^{3}-3(uv^{2}+uw^{2}+vw^{2}+vu^{2})+6v^{2}w+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}}} となる。23という数字は定義多項式の判別式に由来する。 これを用いれば、整数演算によってn番目のペラン数を O ( log ⁡ n ) {\displaystyle O(\log n)} 回の乗算で求めることが出来る。 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 を発見し肯定的に解決された。2番目に小さいペラン擬素数は 904631 = 7 x 13 x 9941 である。10億未満のペラン擬素数は17個存在する。また、無限に多くのペラン擬素数が存在することがJon Granthamによって証明されている。 素数であるペラン数をペラン素数（Perrin prime）と呼ぶ（オンライン整数列大辞典の数列 A074788）。 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, 22584751787583336797527561822649328254745329 2006年5月にE. W. Weissteinが発見した32,147桁のペラン数 P(263226) はおそらくペラン素数であろうと考えられている。