ペラン数
ペラン数(英: Perrin number)とは、以下の漸化式で定義される数である。
また、これによって得られる以下の数列をペラン数列と呼ぶ。
3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39 ... (オンライン整数列大辞典の数列 A001608)
n-頂点の閉路グラフにおける異なる極大独立集合の個数はn番目のペラン数となる 。
となる。23という数字は定義多項式の判別式に由来する。
これを用いれば、整数演算によってn番目のペラン数を O ( log  n ) {\displaystyle O(\log n)} 回の乗算で求めることが出来る。
( 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}}}
素数であるペラン数をペラン素数(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) はおそらくペラン素数であろうと考えられている。