ペラン数のソースを表示

[[File:Perrin triangles.png|thumb|350px|ペラン数列の大きさの辺長を有する[[正三角形]]を並べた図]]
'''ペラン数'''（{{lang-en-short|Perrin number}}）とは、以下の[[漸化式]]で定義される数である。

<math display="block">\begin{align}
&P(0)=3,P(1)=0,P(2)=2,\\
&P(n)=P(n-2)+P(n-3),n>2
\end{align}</math>

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

:[[3]], [[0]], [[2]], 3, 2, [[5]], 5, [[7]], [[10]], [[12]], [[17]], [[22]], [[29]], [[39]] ... （{{OEIS|id=A001608}}）

n-頂点の[[閉路グラフ]]における異なる極大[[独立集合]]の個数は''n''番目のペラン数となる
<ref>*{{cite journal
 | author = Füredi, Z. | authorlink = :en:Zoltán Füredi
 | title = The number of maximal independent sets in connected graphs
 | journal = Journal of Graph Theory
 | volume = 11
 | issue = 4
 | year = 1987
 | pages = 463–470
 | doi = 10.1002/jgt.3190110403}}</ref>。

== 歴史 ==
[[1878年]]には[[エドゥアール・リュカ]]が<ref>*{{cite journal
 | author = Lucas, E.
 | authorlink = エドゥアール・リュカ
 | title = Théorie des fonctions numériques simplement périodiques
 | journal = American Journal of Mathematics
 | volume = 1
 | pages = 197–240
 | year = 1878
 | doi = 10.2307/2369311}}
</ref>、[[1899年]]には{{仮リンク|ラウル・ペラン|fr|Raoul Perrin}}が<ref>*{{cite journal
 | author = Perrin, R.
 | title = Query 1484
 | journal = L'Intermediaire Des Mathematiciens
 | volume = 6
 | pages = 76
 | year = 1899}}
</ref>この数列について言及している。[[1982年]]にはAdamsとShanksがこの数列について詳しく調べ、ペラン数列と名付けた<ref name=adams>*{{cite journal
 | author = Adams, William; Shanks, Daniel
 | title = Strong primality tests that are not sufficient
 | journal = Mathematics of Computation
 | volume = 39
 | year = 1982
 | issue = 159
 | pages = 255–300
 | id = {{MathSciNet | id = 0658231}}
 | doi = 10.2307/2007637}}
</ref>。

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

:<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 (数式処理システム)|magma]]でのコードの例を以下に示す。

 P&lt;x&gt; := PolynomialRing(Rationals());
 S&lt;t&gt; := SplittingField(x^3-x-1); 
 P2&lt;y&gt; := PolynomialRing(S);
 p,q,r := Explode(&#91;r&#91;1&#93; : r in Roots(y^3-y-1)&#93;);
 Mi:=Matrix(&#91;&#91;1/p,1/q,1/r&#93;,&#91;1,1,1&#93;,&#91;p,q,r&#93;&#93;)^(-1);
 T&lt;u,v,w&gt; := PolynomialRing(S,3);
 v1 := ChangeRing(Mi,T) *Matrix(&#91;&#91;u&#93;,&#91;v&#93;,&#91;w&#93;&#93;);
 &#91;p^i*v1&#91;1,1&#93;^3 + q^i*v1&#91;2,1&#93;^3 + r^i*v1&#91;3,1&#93;^3 : i in &#91;-1..1&#93;&#93;;

<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 = 521<sup>2</sup> を発見し<ref name="adams"/>肯定的に解決された。2番目に小さいペラン擬素数は 904631 = 7 x 13 x 9941 である。10億未満のペラン擬素数は17個存在する<ref>{{OEIS|id=A013998}}</ref>。また、無限に多くのペラン擬素数が存在することがJon Granthamによって証明されている<ref>[http://www.pseudoprime.com/pseudo3.pdf There are infinitely many Perrin pseudoprimes], Jon Grantham, Journal of Number Theory (2010).</ref>。

== ペラン素数 ==

[[素数]]であるペラン数を'''ペラン素数'''（Perrin prime）と呼ぶ（{{OEIS|id=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) はおそらくペラン素数であろうと考えられている。

== 注釈、参考文献 ==
{{reflist}}

== 外部リンク ==
* [https://web.archive.org/web/20051108035017/http://www.ai.univie.ac.at/perrin.html Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence]
* {{MathPages|id=home/kmath127/kmath127|title=Lucas and Perrin Pseudoprimes}}
* {{MathPages|id=home/kmath345/kmath345|title=Perrin's Sequence}}
* [http://ntheory.org/primality/perrin.html Perrin Primality Tests]

{{級数}}
{{Classes of natural numbers}}
{{デフォルトソート:へらんすう}}
[[Category:整数の類]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]