ペラン数

ペラン数（）とは、以下の漸化式で定義される数である。

また、これによって得られる以下の数列をペラン数列と呼ぶ。

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... （）

n-頂点の閉路グラフにおける異なる極大独立集合の個数はn番目のペラン数となる
。

歴史
1878年にはエドゥアール・リュカが

、1899年にはR. Perrin が

この数列について言及している。1982年にはAdamsとShanksがこの数列について詳しく調べ、ペラン数列と名付けた
。

母関数
ペラン数列の母関数は以下のようになる。

行列形式

Binetの公式

ペラン数は、以下の方程式の解の累乗を用いて表すことが出来る。

この方程式は3つの解を持ち、1つは実数解（p とする、プラスチック数と呼ばれる）、2つは複素共役な解（q, r とする）である。これらを用いて、フィボナッチ数列におけるBinetの公式と同様の公式を得ることが出来る。

複素解 q, r の絶対値は1より小さいので、 n を大きくすれば q^n, r^n は0に近づく。従って、十分大きな n に対しては、公式は以下のように簡略化出来る。

この公式は、大きな n に対してペラン数を高速に計算するのに用いられる。ペラン数列の連続する項の比は p 、つまりプラスチック数に近づき、その値はおおよそ 1.324718 である。ペラン数列・パドヴァン数列におけるプラスチック数は、フィボナッチ数列における黄金比や、ペル数における白銀比に対応するものとなっている。

乗法公式

Binetの公式を用いて、 G(kn) を G(n−1), G(n) , G(n+1) で表すことが出来る。

であるが、これは  の分解体上の係数を持つ3つの線型方程式であり、逆行列を求めることでを計算することが出来る。これらを 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]];

とすれば

となる。23という数字は定義多項式の判別式に由来する。

これを用いれば、整数演算によって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）と呼ぶ（）。

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) はおそらくペラン素数であろうと考えられている。

注釈、参考文献

外部リンク
Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
MathPages - Lucas Pseudoprimes
MathPages - Perrin's Sequence
Perrin Primality Tests

整数の類
数学に関する記事
数学のエポニム