ペラン数

数学において、ペラン数は特性方程式x ³ = x + 1を持つ二重無限定数再帰 整数列である。ペラン数は、ルーカス数とフィボナッチ数列との関係と同じ関係をパドバン数列にもつ。

ペラン数は再帰関係によって定義される。

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

そしてその逆

${\displaystyle P(n)=P(n+3)-P(n+1){\mbox{ }}n<0の場合。}$

両方向の最初の数項は

ペラン数は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{配列}}}$

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

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

ペラン数列は再帰関係も満たす。これと定義再帰から始めて、例えば無限の数の関係を作り出すことができる。${\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)^{nk}{\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)& =\合計_{k=0}^{n}P(-2k).\end{整列}}}$

ペラン数は、行列の積分べき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),}$

数列の特性方程式が次のように書かれる場合、係数⁠ ⁠はVieta の公式を用いて根で表すことができます。 ${\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.}$

整数a、b、c、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 = 3u _n−1 − 2u _{n−2の連続する項の m に関する剰余を計算すれば十分でしょう。} ^[11] 私は同じ特性を持っていると思われる別の再帰列を見つけました。それは、初期値が v ₀ = 3、v ₁ = 0、v ₂ = 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]

ペラン数列にはフェルマー特性があります。つまり、 pが素数の場合、P(p) ≡ P(1) ≡ 0 (mod p) となります。ただし、逆は成り立ちません。つまり、合成数 nによってはP(n)を割り切れる場合があります。この特性を持つ数はペラン擬素数と呼ばれます。

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

10 ⁹未満の17個のペラン擬素数は

271441、904631、16532714、24658561、27422714、27664033、46672291、102690901、130944133、196075949、214038533、 517697641、545670533、801123451、855073301、903136901、970355431。^[16]

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

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

1982年のアダムスとシャンクスのO(log n)ペラン素数判定^[21]

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

元々 HP-41Cポケット電卓で実行するために考案されたメインの倍精度加算ループは、 nの各ビットに対して 6 回のモジュラー二乗を犠牲にして、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):= 温度
  終わり
     
  P(2t + 2)とP(−2t − 2)
  を配列の両端にコピーし、
  以下の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)
    終了終了
  終了
     
終わり
     
結果
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):= 1
v(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]

• ルーカス、E. (1878)。 「数値的な機能の理論、単純化された時代」。American Journal of Mathematics (フランス語)。1 (3)。ジョンズ・ホプキンス大学出版局: 229–231。土井：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。７． Gauthier-Villars et fils: 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.
• Füredi, Zoltán (1987). 「連結グラフにおける最大独立集合の数」. Journal of Graph Theory . 11 (4): 463–470. doi :10.1002/jgt.3190110403.
• アルノ、スティーブン (1991)。「ペラン擬素数に関する注記」。 計算数学。56 ( 193 )。アメリカ数学会: 371–376。Bibcode : 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
• Stephan, Holger (2020). 「少数の巨大数を含む数百万のペリン擬素数」. arXiv : 2002.03756v1 [math.NA].
• Stephan, Holger (2019). Perrin擬素数 (WIAS研究データNo.4). ベルリン: Weierstrass Institute . doi : 10.20347/WIAS.DATA.4 .

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