ペラン番号

数列 3,0,2,3,2,5,5,7,10,...

ペラン数に等しい辺の長さを持つ正三角形の螺旋。

数学において、ペラン数とは、特性方程式x ³ = x + 1を持つ二重無限定数再帰 整数列である。フランスの技術者ラウル・ペラン [fr]にちなんで名付けられたペラン数は、ルーカス数とフィボナッチ数列の関係と同様に、パドヴァン数列と関係がある。

定義

ペラン数は漸化式によって定義されます

${\displaystyle {\begin{aligned}P(0)&=3,\\P(1)&=0,\\P(2)&=2,\\P(n)&=P(n-2)+P(n-3){\mbox{ for }}n>2,\end{aligned}}}$

そしてその逆

${\displaystyle P(n)=P(n+3)-P(n+1){\mbox{ for }}n<0.}$

両方向の最初の数項は

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
P(n)	3	0	2	3	2	5	5	7	10	12	17	22	29	39	51	68	90	119	… [1]
P(−n)	…	−1	1	2	−3	4	−2	−1	5	−7	6	−1	−6	12	−13	7	5	−18	… [2]

ペラン数は最初の3つの項の和として表すことができます

${\displaystyle {\begin{array}{c|c|c}n&P(n)&P(-n)\\\hline 0&P(0)&...\\1&P(1)&P(2)-P(0)\\2&P(2)&-P(2)+P(1)+P(0)\\3&P(1)+P(0)&P(2)-P(1)\\4&P(2)+P(1)&P(1)-P(0)\\5&P(2)+P(1)+P(0)&-P(2)+2P(0)\\6&P(2)+2P(1)+P(0)&2P(2)-P(1)-2P(0)\\7&2P(2)+2P(1)+P(0)&-2P(2)+2P(1)+P(0)\\8&2P(2)+3P(1)+2P(0)&P(2)-2P(1)+P(0)\end{array}}}$

最初の14個の素ペラン数は

n	2	3	4	5	6	7	10	12	20	21	24	34	38	75	… [3]
P(n)	2	3	2	5	5	7	17	29	277	367	853	14197	43721	1442968193	… [4]

歴史

1876年にエドゥアール・リュカスがこの数列とその方程式について初めて言及しました。リュカスは、 nが素数であれば指数nで項P(n)を割り切れることを指摘しました。^[5] 1899年にラウル・ペラン [fr]はこの性質に反例があるかどうか尋ねました。^[6]合成指数nで割り切れる最初のP(n)は、1982年にウィリアム・アダムスとダニエル・シャンクスによって発見されました。^[7]彼らは数列の詳細な調査を発表し、その続編は4年後に発表されました。^[8]

特性

ペラン関数の縮図：脱出時間アルゴリズムを、ビューポート幅0.05320の臨界点z = 1.225432の周りのペラン関数F(z)全体のニュートン写像に適用します。中心から放射状に広がる吸引域は、F(z) = 0の無限個の実根（左）と複素根（右）に対応します

ペラン列は再帰関係も満たす。これと定義再帰から出発して、例えば無限の数の関係を作り出すことができる。 ${\displaystyle P(n)=P(n-1)+P(n-5).}$ ${\displaystyle P(n)=P(n-3)+P(n-4)+P(n-5).}$

ペラン数列の生成関数は

${\displaystyle {\frac {3-x^{2}}{1-x^{2}-x^{3}}}=\sum _{n=0}^{\infty }P(n)\,x^{n}}$

この数列は二項係数の和と次の関係がある。

${\displaystyle P(n)=n\times \sum _{k=\lfloor (n+2)/3\rfloor }^{\lfloor n/2\rfloor }{\binom {k}{n-2k}}/k,}$^[1]

${\displaystyle P(-n)=n\times \sum _{k=0}^{\lfloor n/3\rfloor }(-1)^{n-k}{\binom {n-2k}{k}}/(n-2k).}$

ペラン数は部分和で表すことができる

${\displaystyle {\begin{aligned}P(n+5)-2&=\sum _{k=0}^{n}P(k)\\P(2n+3)&=\sum _{k=0}^{n}P(2k)\\5-P(4-n)&=\sum _{k=0}^{n}P(-k)\\3-P(1-2n)&=\sum _{k=0}^{n}P(-2k).\end{aligned}}}$

ペラン数は、行列の整数乗n ≥ 0として得られる。

${\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P(n)\\P(n+1)\\P(n+2)\end{pmatrix}},}$

およびその逆

${\displaystyle {\begin{pmatrix}-1&0&1\\1&0&0\\0&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P(-n)\\P(1-n)\\P(2-n)\end{pmatrix}}.}$

フィボナッチ数列のシムソン恒等式のペラン類似体は、行列式で与えられる。

${\displaystyle {\begin{vmatrix}P(n+2)&P(n+1)&P(n)\\P(n+1)&P(n)&P(n-1)\\P(n)&P(n-1)&P(n-2)\end{vmatrix}}=-23.}$

n頂点閉路グラフにおける異なる最大独立集合の数は、 n≥2のn番目のペラン数で数えられる。^[9]

ビネーの公式

ペラン関数は数列を実数に拡張します

漸化式の解は特性方程式の根で表すことができます。3つの解が実根⁠ ⁠（近似値は1.324718で塑性比として知られています）と複素共役根⁠ ⁠および⁠ ⁠である場合、ペラン数はビネの公式を用いて計算でき、この公式は負のnに対しても成り立ちます。 ${\displaystyle P(n)=P(n-2)+P(n-3)}$ ${\displaystyle x^{3}-x-1=0}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle P(n)=\alpha ^{n}+\beta ^{n}+\gamma ^{n},}$

極形式は、 nが正または負の大きい場合、式は第1項または第2項のいずれかに逐次簡約されるため、負の添え字を持つ数は振動します。αが十分な精度で計算されていれば、これらの式は大きなnに対するペラン数を計算するのに使用できます。 ${\displaystyle P(n)=\alpha ^{n}+2\cos(n\,\theta ){\sqrt {\alpha ^{-n}}},}$ ${\displaystyle \theta =\arccos(-{\sqrt {\alpha ^{3}}}/2).}$ ${\displaystyle \lim _{n\to \infty }\alpha ^{-n}=0,}$

恒等式を展開すると、シーケンスの前方部分と後方部分がリンクされる重要なインデックス倍増規則が得られます。 ${\displaystyle P^{2}(n)=(\alpha ^{n}+\beta ^{n}+\gamma ^{n})^{2}}$ ${\displaystyle P(2n)=P^{2}(n)-2P(-n),}$

素指数pを割り切るP(p)

数列の特性方程式が次のように書かれると、係数はヴィエタの公式を用いて根で表すことができます。 ${\displaystyle f(x)=x^{3}-\sigma _{1}x^{2}+\sigma _{2}x-\sigma _{3}}$ ${\displaystyle \sigma _{k}}$ ${\displaystyle \alpha ,\beta ,\gamma }$

${\displaystyle {\begin{alignedat}{3}\sigma _{1}&=\alpha +\beta +\gamma &&=0\\\sigma _{2}&=\alpha \beta +\alpha \gamma +\beta \gamma &&=-1\\\sigma _{3}&=\alpha \beta \gamma &&=1.\end{alignedat}}}$

これらの整数値関数は、 ${\displaystyle \alpha ,\beta ,\gamma .}$

• 対称多項式の基本定理は、単項関数の ${\displaystyle f}$複素根のすべての対称多項式は、整数係数の別の多項式関数として表すことができることを述べています。 ${\displaystyle f.}$
• 多項式係数に対するルーカスの定理の類似は、 ⁠ ⁠ならば素数⁠ ⁠で割り切れるというものである。 ${\displaystyle {\frac {p!}{i!j!k!}}}$ ${\displaystyle i,j,k<p}$ ${\displaystyle {\binom {p}{i,j,k}}}$ ${\displaystyle p.}$

与えられた整数⁠ ⁠ ${\displaystyle a,b,c}$と⁠ ⁠ ${\displaystyle n>0,}$

${\displaystyle (a+b+c)^{n}=\sum _{i+j+k=n}{\binom {n}{i,j,k}}a^{i}b^{j}c^{k}.}$

指数i、j、kを並べ替えて、対称単項式加数に並べ替えます。

${\displaystyle (a+b+c)^{n}-(a^{n}+b^{n}+c^{n})=}$ ${\displaystyle \sum _{\begin{aligned}i\leq j\leq k&<n\\i+j+k&=n\end{aligned}}{\binom {n}{i,j,k}}\sum _{\pi (i,j,k)}a^{i}b^{j}c^{k}.}$

べき乗を素数 ${\displaystyle p}$、 ${\displaystyle n}$整数を複素根に置き換え、すべての対称多項式関数について を用いた表現を計算します。例えば、はであり、べき乗和はニュートンの再帰的スキームを用いて係数 で表すことができます。したがって、恒等式は整数項を持ち、両辺が素数 で割り切れることがわかります。 ${\displaystyle \alpha ,\beta ,\gamma }$ ${\displaystyle a,b,c}$ ${\displaystyle \sigma _{1},\sigma _{2},\sigma _{3}}$ ${\displaystyle (\alpha +\beta +\gamma )^{p}}$ ${\displaystyle \sigma _{1}^{p}=0}$ ${\displaystyle \alpha ^{p}+\beta ^{p}+\gamma ^{p}=P(p)}$ ${\displaystyle \sigma _{k}}$ ${\displaystyle p.}$

素数が ${\displaystyle p}$逆順に割り切れることを示すには、特性方程式を ${\displaystyle P(-p)+1}$反転させる必要があります。その場合、根が係数となり、同様の推論が適用されます。 ${\displaystyle \alpha ^{-1},\beta ^{-1},\gamma ^{-1},}$ ${\displaystyle \sigma _{1}=-1,\sigma _{2}=0,\sigma _{3}=1,}$

ペラン素数判定

質問 1484 。質問 1401 ^[10]の対象となっている中国起源の興味深い命題は、もしそれが真であれば、与えられた数mが素数かどうかを検証するためのウィルソンの定理よりも実際的な基準を提供するであろう。それは、初期値u ₀ =−1、u ₁ = 0を持つ再帰列u _n = 3 u _n−1 − 2 u _{n−2の連続する項の}mに関する剰余を計算すれば十分であろう^{。 [11]}私は同じ特性を持っていると思われる別の再帰列を見つけた。それは、初期値 v 0 = 3、v 1 = 0、v 2 = 2 を持つ一般項が v n = v n−2 + v n−3 であるもの_である。n_が素数で_あれば、_v nが_nで割り切れる_ことは簡単に_証明できる。私は、 nのかなり大きな値まで、逆の場合は割り切れないことを検証した。しかし、これが本当にそうであるかどうかを知ることは興味深い。特に、数列v _{n は}数列u _nよりもはるかに緩やかな増加を示す（例えばn = 17の場合、u _n = 131070、v _n = 119となる）。これはnが大きな数であるときの計算を簡素化する。一方の数列に適用できる同じ証明は、もし前述の性質が両方に当てはまるならば、間違いなくもう一方の数列にも当てはまる。問題はそれを発見することだけである。^[12]

ペラン数列にはフェルマー特性があります。つまり、 ⁠ ⁠ ${\displaystyle p}$が素数の場合、 ⁠ ⁠が素数になります。ただし、逆は成り立ちません。一部の合成数は⁠ ⁠を割り切れる場合があります。この特性を持つ数はペラン擬素数と呼ばれます。 ${\textstyle P(p)\equiv P(1)\equiv 0{\pmod {p}}.}$ ${\displaystyle n}$ ${\displaystyle P(n).}$

ペラン擬素数の存在については、マロとジャーデンによって検討されたが^[13] 、アダムスとシャンクスが最小の擬素数（P(271441)は33150桁の十進数）を発見するまで、その存在は知られていなかった。^[14]ジョン・グランサムは後に、ペラン擬素数が無限に存在することを証明した。^[15] ${\displaystyle 271441=521^{2}}$

10⁻⁻以下の17個^のペラン擬素数は
、271441、904631、16532714、24658561、27422714、27664033、46672291、102690901、130944133、196075949、214038533、517697641、545670533、801123451、855073301、903136901、970355431である。 ^[16]

アダムズとシャンクスは、素数は合同性も満たすことを指摘した。両方の性質が成り立つ合成数は制限ペラン擬素数と呼ばれる。10の9^乗未満のそのような数は9つしかない。^{[17] [18] [19]} ${\textstyle P(-p)\equiv P(-1)\equiv -1{\pmod {p}}.}$

ペラン擬素数は稀ですが、フェルマー擬素数と重複しています。上記の17個の数のうち4個は、基数2のフェルマート数でもあります。一方、ルーカス擬素数は反相関しています。^[20]おそらく、ペランテストとルーカステストを組み合わせることで、既知の擬素数が存在しない信頼性の高いBPSWテストと同等の強力な素数判定が可能になるはずですが、計算コストは​​高くなります。

擬似コード

1982年のアダムズとシャンクス・ペラン素数判定^[21] ${\displaystyle O(\log n)}$

2つの整数配列u(3)とv(3)は、 u( )の正のインデックスt = 0、1、2、 v( )の負のインデックスt = 0、−1、−2を持つペラン数列の最小項に初期化されます。

元々はHP-41Cポケット電卓で実行するために考案されたメインの倍精度加算ループは、 nの各ビットに対して 6 回のモジュラー 2 乗を犠牲にして、 P(n) mod nと逆のP(−n) mod nを計算します。

ペラン数の添え字は、P(2t) = P ² (t) − 2P(−t)という恒等式を用いて2倍にされる。その結果生じるP(±2t)とP(±2t ± 2)の間の差は、定義関係P(t) = P(t − 2) + P(t − 3) を適用することで埋められる。

初期値int  u(0):= 3, u(1):= 0, u(2):= 2 int v(0):= 3, v(1):=−1, v ( 2): = 1  奇数の正の数 n をテストするint nを入力する   int h:= nの最上位ビットを設定する k := h − 1 から0まで  6つのペラン数 のインデックスを2倍します。i = 0, 1, 2 温度:= u(i)^2 − 2v(i) (nを法として) v(i):= v(i)^2 − 2u(i) (nを法として) u(i):= 温度 endfor P(2t + 2)とP(-2t - 2) を配列のendsにコピーし、 以下のif文で使用します u(3):= u(2) v(3):= v(2) P(2t ± 2)をP(2t ± 1)で上書きする 温度:= u(2) − u(1) u(2):= u(0) + 温度 u(0):= 温度 P(−2t ± 2)をP(−2t ± 1)で上書きする 温度:= v(0) − v(1) v(0):= v(2) + 温度 v(2):= 温度 nのビットkが設定されている場合は、両方のPerrinトリプル のインデックスを 1ずつ 増やします。i = 0, 1, 2の場合 u(i):= u(i + 1) v(i):= v(i + 1) endfor  endif endfor 結果v(2), v(1), v(0)を出力u(0), u(1), u(2) を出力

続いてP(−n − 1)、P(−n)、P(−n + 1)、P(n − 1)、P(n)、P(n + 1) (mod n)。

P(−n) = −1かつP(n) = 0の場合、 nは確率的に素数、つまり実際に素数であるか、または制限されたペラン擬素数です。

Shanksらは、彼らが発見したすべての制限擬素数について、上記の6つのレジスタの最終状態（nの「署名」 ）が初期状態1,−1,3,3,0,2に等しいことを観察した。^{[22]すべての素数の}≈1 / 6でも同じことが起こるため、このテストだけでは2つの集合を区別することはできない。^[23]これらのケースでは、彼らは再帰関係A(n) = A(n − 1) + A(n − 3)と初期値を 持つNarayana-Lucas姉妹列も使用することを推奨している。

u(0):= 3, u(1):= 1, u(2):= 1v(0):= 3、v(1):= 0、v(2):=−2

同じ倍数ルールが適用され、ギャップを埋める公式は次のようになります。

温度:= u(0) + u(1)u(0):= u(2) − 温度u(2):= 温度 温度:= v(2) + v(1)v(2):= v(0) − 温度v(0):= 温度

ここで、A(−n) = 0かつA(n) = 1のとき、 nは素数である可能性が高い。

カーツらは、50∙10⁻⁻^以下の2つの数列の奇数擬素数に重複がないことを発見し、2,277,740,968,903 = 1067179∙2134357が両方のテストに合格する最小の合成数であると仮定した。^[24]

3次のペル・ルーカス回帰式 A(n) = 2A(n − 1) + A(n − 3)も使用すると、この境界は4,057,052,731,496,380,171 = 1424263447 ∙ 2848526893まで押し上げられる。^[25]

さらに、 -1または3以外の倍加則合同の根は、ミラー・ラビンテストにおける1の非自明な平方根のような合成数を明らかにします。^[26]これにより、各シーケンスの制限付き擬素数の数が約 3 分の 1 に削減され、特にカーマイケル数の検出に効率的です。[ 27 ^] ${\displaystyle x^{2}-2x\equiv 3=P(0){\pmod {n}}\,}$

最も弱い制限ペラン擬素数は46672291であり、上記の2つの境界は173,536,465,910,671と79,720,990,309,209,574,421に順次拡張される。^[28]

注釈

1. Sloane, N. J. A. (編). 「数列 A001608 (ペラン数列（またはオンドレイ・サッチ数列）：a(n) = a(n-2) + a(n-3)、ただしa(0) = 3、a(1) = 0、a(2) = 2)」.オンライン整数数列百科事典. OEIS財団
2. Sloane, N. J. A. (編). 「数列 A078712 ((-3 - 2*x)/(1 + x - x^3) の x 乗における級数展開)」.オンライン整数数列百科事典. OEIS Foundation.
3. Sloane, N. J. A. (編). 「数列A112881（素数ペラン数の指数；A001608(n)が素数となるnの値）」.オンライン整数数列百科事典. OEIS財団.
4. Sloane, N. J. A. (編). 「数列A074788（ペラン数列b(n+1) = b(n-1) + b(n-2)における素数、初期値b(1)=3、b(2)=0、b(3)=2）」.オンライン整数数列百科事典. OEIS財団.
5. ルーカス（1878）
6. ペラン（1899）
7. アダムス＆シャンクス（1982）
8. カーツ、シャンクス、ウィリアムズ（1986）
9. フューレディ（1987）
10. タリー（1898）
11. Sloane, N. J. A. (編). 「Sequence A000918 (a(n) = 2^n − 2)」.オンライン整数列百科事典. OEIS財団.
12. ペラン（1899）フランス語からの翻訳
13. マロ（1900）、ジャーデン（1966）
14. アダムス＆シャンクス（1982年、255ページ）
15. グランサム（2010）、ステファン（2020）
16. Sloane, N. J. A. (編). 「数列A013998 (無制限ペラン擬素数)」.オンライン整数数列百科事典. OEIS財団.
17. Sloane, N. J. A. (編). 「数列A018187 (制限付きペラン擬素数)」.オンライン整数数列百科事典. OEIS財団.
18. Sloane, N. J. A. (編). 「数列A275612（制限付きペラン擬素数（アダムズとシャンクスの定義））」.オンライン整数数列百科事典. OEIS財団.
19. Sloane, N. J. A. (編). 「数列A275613（制限付きペラン擬素数（グランサム定義））」.オンライン整数数列百科事典. OEIS財団.
20. Dana Jacobsen (2020) がリストした10 ¹⁵未満の 2402549 個のルーカス・セルフリッジ擬素数はいずれもペラン擬素数ではない。
21. アダムス＆シャンクス（1982年、265、269-270ページ）
22. Adams & Shanks (1982, p. 275), Kurtz, Shanks & Williams (1986, p. 694). これは後にSteven Arno (1991)によってn < 10 ^{14の場合に確認された。}
23. 署名は残りの2種類の素数に関する識別情報を提供します。例えば、Holger Stephan (2019) によって計算された最小のQ型擬素数 50,972,694,899,204,437,633 は、Adams & Shanks (1982, p. 257) の署名条件 14a および 14c によって明らかになります。
24. カーツ、シャンクス、ウィリアムズ（1986年、697ページ）
25. ステファン（2019）
26. アダムス＆シャンクス（1982年、280-283ページ）
27. 拡張 Perrin テストの C/C++ 実装については、この記事の以前のバージョンの最後のサブセクションを参照してください。
28. ステファン（2019）

参考文献

• ルーカス, E. (1878). 「単純な周期的数値関数理論」. American Journal of Mathematics (フランス語). 1 (3). ジョンズ・ホプキンス大学出版局: 229–231 . doi : 10.2307/2369311 . JSTOR  2369311
• タリー、G. (1898)。 「質問1401」。L'Intermédiaire des Mathématiciens。５．ゴーティエ・ヴィラール他：266–267。
• ペリン、R. [フランス語] (1899)。 「質問1484」。L'Intermédiaire des Mathématiciens。６．ゴーティエ・ヴィラールとフィル：76–77。
• マロ、E. (1900)。 「応答 à 1484」。L'Intermédiaire des Mathématiciens。７．ゴーティエヴィラール他: 280–282、312–314 。
• ドブ・ジャーデン（1966年）。反復シーケンス(PDF) (第 2 版)。エルサレム：リベオン・ルマテマティカ。86～ 93ページ 。
• ウィリアム・アダムス、ダニエル・シャンクス(1982). 「十分ではない強い素数判定」.計算数学. 39 (159).アメリカ数学会: 255–300 . doi : 10.1090/S0025-5718-1982-0658231-9 . JSTOR  2007637.
• Kurtz, GC; Shanks, Daniel ; Williams, HC (1986). 「50∙109未満の数の素数判定の高速化」.計算数学. 46 (174).アメリカ数学会: 691–701 . doi : 10.1090/S0025-5718-1986-0829639-7 . JSTOR  2008007.
• フューレディ、ゾルタン(1987). 「連結グラフにおける最大独立集合の数」.グラフ理論ジャーナル. 11 (4): 463– 470. doi :10.1002/jgt.3190110403.
• アルノ, スティーブン (1991). 「ペラン擬素数に関する注記」.計算数学. 56 (193).アメリカ数学会: 371–376 .書誌コード:1991MaCom..56..371A. doi : 10.1090/S0025-5718-1991-1052083-9 . JSTOR  2008548.
• グランサム、ジョン (2010). 「ペラン擬素数は無限に存在する」.数論ジャーナル. 130 (5): 1117– 1128. arXiv : 1903.06825 . doi :10.1016/j.jnt.2009.11.008.
• Jacobsen, Dana (2020). 「擬素数の統計と表」ntheory.org . 2024年3月7日閲覧。#LPSP Lucas-Selfridge
• ステファン、ホルガー (2020). 「少数の巨大素数を含む数百万のペラン擬素数」. arXiv : 2002.03756v1 [math.NA].
• ステファン・ホルガー (2019). ペラン擬素数 (WIAS研究データNo.4). ベルリン:ヴァイエルシュトラス研究所. doi : 10.20347/WIAS.DATA.4 .

外部リンク

• ジェイコブセン、ダナ (2016).「ペラン素数判定」
• ライト、コリン (2015). 「ペラン擬素数の発見」
• 「ペランの数列」。MathPages.com。
• 「ルーカスとペラン擬素数」MathPages.com。
• ホルツバウア、クリスチャン (1997)。 「ペリン擬似素数」。
• ターク、リチャード（2014）「ペラン黒板」

Retrieved from "https://en.wikipedia.org/w/index.php?title=Perrin_number&oldid=1315781308"