ピサーノ時代

数論において、n次ピサーノ周期はπ ( n )と表記され、 n を法とするフィボナッチ数列が繰り返される周期である。ピサーノ周期は、フィボナッチとして知られるレオナルド・ピサーノにちなんで名付けられている。フィボナッチ数列の周期関数の存在は、1774 年にジョゼフ・ルイ・ラグランジュによって指摘された。^{[1] [2]}

フィボナッチ数列は次の整数列の数字です。

0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、4181、6765、10946、17711、28657、46368、...（OEISのシーケンスA000045）

再帰関係によって定義される

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1}$

${\displaystyle F_{i}=F_{i-1}+F_{i-2}.}$

任意の整数 nについて、 n を法とするフィボナッチ数列F _{i は}周期的である。ピサノ周期はπ ( n ) で表され、この数列の周期の長さである。たとえば、 3 を法とするフィボナッチ数列は次のように始まる。

0、1、1、2、0、2、2、1、0、1、1、2、0、2、2、1、0、1、1、2、0、2、2、1、0、... (OEISのシーケンスA082115 )

この数列の周期は8なので、π (3) = 8です。

π (2) = 3を除いて、ピサノ周期π ( n )は常に偶数である。このことは、 π ( n )がフィボナッチ行列の次数に等しいことを観察することで証明できる。

${\displaystyle \mathbf {Q} ={\begin{bmatrix}1&1\\1&0\end{bmatrix}}}$

nを法とする有限整数環上の可逆な2 行 2列行列の一般線型群 において、 Q は行列式 −1 を持つので、 Q ^{π ( n )}の行列式は(−1) ^{π ( n )}であり、これは では 1 に等しくなければならないので、n ≤ 2 かπ ( n ) が偶数である。^[3]${\displaystyle {\text{GL}}_{2}(\mathbb {Z} _{n})}$ ${\displaystyle \mathbb {Z} _{n}}$${\displaystyle \mathbb {Z} _{n}}$

および なので、と で割り切れます。 ${\displaystyle F_{0}=0}$${\displaystyle F_{1}=1}$${\displaystyle n}$${\displaystyle F_{\pi (n)}}$${\displaystyle (F_{\pi (n)+1}-1)}$

mとn が互いに素である場合、中国剰余定理により、π ( mn ) はπ ( m ) とπ ( n )の最小公倍数です。たとえば、π (3) = 8 およびπ (4) = 6 はπ (12) = 24 を意味します。したがって、ピサノ周期の研究は、k ≥ 1 の素数累乗q  =  p ^kのピサノ周期の研究に還元できます。

pが素数の場合、π ( p ^k ) はp ^{k –1}  π ( p ) を割り切れます。 すべての素数pと整数k > 1 に対してかどうかは不明です。 反例となる任意の素数p は必ずWall–Sun–Sun 素数となり、逆に任意の Wall–Sun–Sun 素数p は反例となります ( k = 2 と設定)。 ${\displaystyle \pi (p^{k})=p^{k-1}\pi (p)}$

したがって、ピサノ周期の研究は、素数のピサノ周期の研究にまでさらに縮小される可能性があります。この点で、2 つの素数は異常です。素数 2 は奇数のピサノ周期を持ち、素数 5 は他の素数のピサノ周期よりも比較的大きな周期を持ちます。これらの素数のべき乗の周期は次のとおりです。

• n  = 2 ^kの場合には、π ( n ) = 3·2 ^{k –1} = ⁠3·2^キロ/2⁠ = ⁠3位/2⁠ .
• n  = 5 ^kの場合、π ( n ) = 20·5 ^{k –1} = ⁠20·5^キロ/5⁠ = 4 n .

これらのことから、n = 2  ·  5 ^kの場合、 π ( n ) = 6 nとなる。

残りの素数はすべて剰余類またはに属します。p が2 および 5 以外の素数である場合、ビネの公式のp を法とした類似物は、 π ( p ) がp を法とするx ² − x − 1の根の乗法順序であることを意味します。 の場合、これらの根は (二次の相互性により)に属します。したがって、それらの順序π ( p ) はp − 1の約数です。たとえば、π (11) = 11 − 1 = 10 およびπ (29) = (29 − 1)/2 = 14 です。 ${\displaystyle p\equiv \pm 1{\pmod {10}}}$${\displaystyle p\equiv \pm 3{\pmod {10}}}$${\displaystyle p\equiv \pm 1{\pmod {10}}}$${\displaystyle \mathbb {F} _{p}=\mathbb {Z} /p\mathbb {Z} }$

x ² − x − 1のp を法とする根が（再び二次の相互性により）に属さず、有限体に属する場合${\displaystyle p\equiv \pm 3{\pmod {10}},}$${\displaystyle \mathbb {F} _{p}}$

${\displaystyle \mathbb {F} _{p}[x]/(x^{2}-x-1).}$

フロベニウスの自己同型は これらの根を交換するので、 rとsで表すとr ^p = sとなり、r ^{p +1} = –1 となります。つまり、r ^{2( p +1)} = 1 であり、rの位数であるピサーノ周期は、 2( p +1)を奇数で割った商です。この商は常に 4 の倍数です。π ( p ) が 2( p +1)より小さいpの最初の例は、π (47) = 2(47 + 1)/3 = 32、π (107) = 2(107 + 1)/3 = 72、 π (113) = 2(113 + 1)/3 = 76 です (下の表を参照)。 ${\displaystyle x\mapsto x^{p}}$

上記の結果から、n = p ^kが奇数の素数累乗でπ ( n ) > nである場合、π ( n )/4 はnより大きくない整数であることがわかります。ピサノ周期の乗法特性は、

π ( n ) ≤ 6 nであり、 n = 2 · 5 ^r （ r ≥ 1）の場合にのみ等式となる。 ^[4]

最初の例はπ (10) = 60とπ (50) = 300です。nが2 · 5 ^rの形式でない場合は、π ( n ) ≤ 4 nとなります。

ピサーノの最初の12周期（OEISのシーケンスA001175）とその周期（読みやすくするためにゼロの前にスペースを入れている）は^[5]である（それぞれ10と11に16進数暗号AとBを使用）。

ピサーノの最初の 144 の期間は次の表に示されています。

n = F (2 k ) ( k ≥ 2)の場合、π( n ) = 4 k です。n = F ( 2 k + 1 )  ( k ≥ 2) の場合、π( n ) = 8 k  + 4 です。つまり、モジュロ ベースが偶数インデックスのフィボナッチ数 (≥ 3) の場合、周期はインデックスの 2 倍になり、サイクルには 2 つのゼロがあります。ベースが奇数インデックスのフィボナッチ数 (≥ 5) の場合、周期はインデックスの 4 倍になり、サイクルには 4 つのゼロがあります。

n = L (2 k ) ( k ≥ 1)の場合、π( n ) = 8 k です。n = L ( 2 k + 1 )  ( k ≥ 1) の場合、π( n ) = 4 k  + 2 です。つまり、モジュロ基数が偶数インデックスのルーカス数 (≥ 3) の場合、周期はインデックスの 4 倍になります。基数が奇数インデックスのルーカス数 (≥ 4) の場合、周期はインデックスの 2 倍になります。

k が偶数の場合、サイクルには 2 つのゼロがあります。kが奇数の場合、サイクルには 1 つのゼロのみがあり、サイクルの後半部分 (もちろん 0 の左側の部分に相当) は、数F (2 m  + 1) とn  −  F (2 m ) が交互に現れ、mが減少する構成になります。

1 サイクルあたりの 0 の出現回数は 1、2、または 4 です。0、1の組み合わせの後の最初の 0 の後の数字をpとします。0 間の距離をqとします。

• p = 1の場合、サイクル内に 0 が 1 つあることは明らかです。これは、 q が偶数であるか、nが 1 または 2 の 場合にのみ可能です。
• それ以外の場合、 p ² ≡ 1であれば、サイクル内に 0 が 2 つあります。これは、 qが偶数の 場合にのみ可能です。
• それ以外の場合、サイクル内に 0 が 4 つあります。qが奇数で、nが1 でも 2 でもない場合に該当します。

一般化されたフィボナッチ数列（同じ再帰関係を満たすが、初期値が異なる、たとえばルーカス数列）の場合、1 サイクルあたりの 0 の出現回数は 0、1、2、または 4 です。

nのピサノ周期とサイクル内のn を法とするゼロの数の比は、 nの出現順位またはフィボナッチエントリポイントを与えます。つまり、n がF ( k )を割り切る最小のインデックスk です。これらは次のとおりです。

1、3、4、6、5、12、8、6、12、15、10、12、7、24、20、12、9、12、18、30、8、30、24、12、25、21、36、24、14、60、30、24、20、9、40、12、19、18、28、30、20、24、44、30、60、24、16、12 、... (OEIS のシーケンスA001177 )

ルノーの論文では、零点の数はF mod mの「位数」と呼ばれ、 と表記され、「出現の順位」は「位数」と呼ばれ、 と表記される。^[6]${\displaystyle \omega (m)}$${\displaystyle \alpha (m)}$

ウォールの予想によれば、が素因数分解できる場合、となる。^[6]${\displaystyle \alpha (p^{e})=p^{e-1}\alpha (p)}$${\displaystyle m}$ ${\displaystyle m=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{n}^{e_{n}}}$${\displaystyle \alpha (m)=\operatorname {lcm} (\alpha (p_{1}^{e_{1}}),\alpha (p_{2}^{e_{2}}),\dots ,\alpha (p_{n}^{e_{n}}))}$

ルーカス数のピサノ周期は

1、3、8、6、4、24、16、12、24、12、10、24、28、48、8、24、36、24、18、12、16、30、48、24、20、84、72、48、14、24、30、48、40、36、16、24、76、18、56、12、40、48、88、30、24、48、32 、... ( OEIS のシーケンスA106291 )

ペル数（または2-フィボナッチ数） のピサノ周期は

1、2、8、4、12、8、6、8、24、12、24、8、28、6、24、16、16、24、40、12、24、24、22、8、60、28、72、12、20、24、30、32、24、16、12、24、76、40、56、24、10、24、88、24、24、22、46、16 、... (OEIS のシーケンスA175181 )

3-フィボナッチ数の ピサノ周期は

1、3、2、6、12、6、16、12、6、12、8、6、52、48、12、24、16、6、40、12、16、24、22、12、60、156、18、48、28、12、64、48、8、48、48、6、76、120、52、12、28、48、42、24、12、66、96、24 、...（OEIS のシーケンスA175182 ）

ヤコブスタール数（または（1,2）-フィボナッチ数） のピサノ周期は

1、1、6、2、4、6、6、2、18、4、10、6、12、6、12、2、8、18、18、4、6、10、22、6、20、12、54、6、28、12、10、2、30、8、12、18、36、18、12、4、20、6、14、10、36、22、46、6 、... (OEIS のシーケンスA175286 )

（1,3）フィボナッチ数の ピサノ周期は

1、3、1、6、24、3、24、6、3、24、120、6、156、24、24、12、16、3、90、24、24、120、22、6、120、156、9、24、28、24、240、24、120、48、24、6、171、90、156、24、336、24、42、120、24、66、736、12 、...（OEIS のシーケンスA175291）

トリボナッチ数（または3段階フィボナッチ数） のピサノ周期は

1、4、13、8、31、52、48、16、39、124、110、104、168、48、403、32、96、156、360、248、624、220、553、208、155、168、117、48、140、1612、331、64、1430、96、1488、312、469、360、2184、496、560、624、308、440、1209、2212、46、416 、 ...（OEIS )

テトラナッチ数（または4段階フィボナッチ数） のピサノ周期は

1、5、26、10、312、130、342、20、78、1560、120、130、84、1710、312、40、4912、390、6858、1560、4446、120、12166、 260、1560、420、234、1710、280、1560、61568、80、1560、24560、17784、390、1368、34290、1092、1560、240、22230、 162800、120、312、 60830、103822、520、...（OEISの配列A106295）

フィボナッチ数列の一般化も参照してください。

ピサーノ周期は代数的整数論を用いて解析することができます。

をkフィボナッチ数列F _k ( n )のn番目のピサノ周期とします ( k は任意の自然数で、これらの数列はF _k (0) = 0、F _k (1) = 1と定義され、任意の自然数n > 1 に対して、F _k ( n ) = kF _k ( n −1) + F _k ( n −2) となります)。mとn が互いに素であれば、中国剰余定理により、 となります。つまり、2 つの数がmn を法として合同であるためには、m を法として合同であり、n を法として合同である場合に限ります (ただし、nとm は互いに素であると仮定します)。たとえば、そしてとなるため、素数べき乗のピサノ周期を計算すれば十分である（通常、、ただしpがk - Wall–Sun–Sun 素数、またはk -フィボナッチ–ヴィーフェリッヒ素数、つまりp ^2がF _k ( p  − 1) またはF _k ( p  + 1)を割り切る場合は除く。ここでF _kはk -フィボナッチ数列であり、たとえば 241 は 3-Wall–Sun–Sun 素数である。241 ^{2 は}F ₃ (242)を割り切るからである。） ${\displaystyle \pi _{k}(n)}$${\displaystyle \pi _{k}(m\cdot n)=\mathrm {lcm} (\pi _{k}(m),\pi _{k}(n))}$${\displaystyle \pi _{1}(3)=8}$${\displaystyle \pi _{1}(4)=6,}$${\displaystyle \pi _{1}(12=3\cdot 4)=\mathrm {lcm} (\pi _{1}(3),\pi _{1}(4))=\mathrm {lcm} (8,6)=24.}$ ${\displaystyle q=p^{n}.}$${\displaystyle \pi _{k}(p^{n})=p^{n-1}\cdot \pi _{k}(p)}$

素数pについては、ビネの公式を使って解析することができます。

${\displaystyle F_{k}\left(n\right)={{\varphi _{k}^{n}-(k-\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}}={{\varphi _{k}^{n}-(-1/\varphi _{k})^{n}} \over {\sqrt {k^{2}+4}}},\,}$k番目の金属平均はどこにあるか${\displaystyle \varphi _{k}}$

${\displaystyle \varphi _{k}={\frac {k+{\sqrt {k^{2}+4}}}{2}}.}$

k ²  + 4 がp を法とする平方剰余（ただし p > 2 かつp は k 2 + 4 を割り切れない）である場合、およびはp^を 法とする整数として表すことができ、したがってビネの公式はpを法とする整数 に対して表すことができ、したがってピサーノ周期はトーティエントを割り切れます。これは、任意のべき乗（ など）は を割り切れる周期を持つためであり、これはp を法とする単位群の位数です。 ${\displaystyle {\sqrt {k^{2}+4}},1/2,}$${\displaystyle k/{\sqrt {k^{2}+4}}}$ ${\displaystyle \phi (p)=p-1}$${\displaystyle \varphi _{k}^{n}}$${\displaystyle \phi (p),}$

k = 1の場合、これはp = 11のときに最初に発生し、4 ²  = 16 ≡ 5 (mod 11)、2 · 6 = 12 ≡ 1 (mod 11)、4 · 3 = 12 ≡ 1 (mod 11)なので、4 =  √ 5、6 = 1/2、1/ √ 5  = 3となり、φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11)となり、合同

${\displaystyle F_{1}\left(n\right)\equiv 3\cdot \left(8^{n}-4^{n}\right){\pmod {11}}.}$

周期がp  −1を適切に割り切れることを示す別の例はπ1（29）=14 _です。

k ^{2 + 4 が}p を 法とする平方剰余でない場合、ビネの公式は代わりに二次拡大体上で定義されます。この体にはp ²個の元があり、したがってその単位群の位数はp ²  − 1 であり、したがってピサーノ周期はp ²  − 1 を割り切ります。たとえば、p = 3 の場合、 π ₁ (3) = 8 となり、3 2 − 1 = 8 に等しくなります_{。p = 7 の場合、π 1}  ( ⁷  )  = 16 となり、7 2 − 1 = 48 を適切に割り切り^ます 。 ${\displaystyle (\mathbb {Z} /p)[{\sqrt {k^{2}+4}}]}$

この解析は、 p = 2でp がk ² + 4の平方自由部分の約数である場合は失敗します 。これらの場合 は零約数であるため、1/2 または の解釈には注意が必要です 。p = 2 の場合、 k 2 ⁺  4は 1 mod 2 に合同です ( kが奇数の場合) が、ピサーノ周期はp  − 1 = 1 ではなく、3 です (実際、これはk が偶数の場合も 3 です)。p が k 2 + 4 の平方自由部分を割り切る場合、ピサーノ^周期は π k ₍ k 2 ⁺  4) = p ²  −  p = p ( p − 1) であり、 p  − 1 またはp ² − 1 を割り切りません 。 ${\displaystyle {\sqrt {k^{2}+4}}}$

フィボナッチ整数列をnを法として考えることができます。言い換えると、環Z / n Z内のフィボナッチ列を考えることができます。周期は π( n )の約数です。サイクルあたりの 0 の発生回数は、0、1、2、または 4 です。nが素数でない場合、サイクルには約数のサイクルの倍数が含まれます。たとえば、n = 10 の場合、追加のサイクルには、 n = 2 の 5 倍と、n = 5 の 2 倍が含まれます。

追加サイクルの表: (元のフィボナッチ サイクルは除外) (それぞれ 10 と 11 に X と E を使用)

n を法とするフィボナッチ整数サイクルの数は次のとおりです。

1、2、2、4、3、4、4、8、5、6、14、10、7、8、12、16、9、16、22、16、29、28、12、30、13、14、14、22、63、24、34、32、39、34、30、58、19、86、32、52、43、58、22、78、39、46、70、102 、...（OEISのシーケンスA015134 ）

• ブルーム、DM (1965)、「一般化フィボナッチ数列の周期性」、アメリカ数学月刊誌、72 (8): 856–861、doi :10.2307/2315029、JSTOR  2315029、MR  0222015
• ブレント、リチャード P. (1994)、「一般化フィボナッチ数列の周期について」、計算数学、63 (207): 389–401、arXiv : 1004.5439、Bibcode :1994MaCom..63..389B、doi :10.2307/2153583、JSTOR  2153583、MR  1216256、S2CID  1038296
• エングストロム、HT (1931)、「線形再帰関係によって定義されるシーケンスについて」、Trans. Am. Math. Soc.、33 (1): 210–218、doi : 10.1090/S0002-9947-1931-1501585-5、JSTOR  1989467、MR  1501585
• ファルコン、S.; プラザ、A. (2009)、「k-フィボナッチ数列モジュロm」、カオス、ソリトン、フラクタル、41 (1): 497–504、Bibcode :2009CSF....41..497F、doi :10.1016/j.chaos.2008.02.014
• Freyd, Peter; Brown, Kevin S. (1992)、「問題と解答: 解答: E3410」、Amer. Math. Monthly、99 (3): 278–279、doi :10.2307/2325076、JSTOR  2325076
• Laxton, RR (1969)、「線形回帰群について」、デューク数学ジャーナル、36 (4): 721–736、doi :10.1215/S0012-7094-69-03687-4、MR  0258781
• ウォール、DD (1960)、「m を法とするフィボナッチ数列」、アメリカ数学月刊誌、67 (6): 525–532、doi :10.2307/2309169、JSTOR  2309169
• ウォード、モーガン(1931)、「線形再帰関係を満たす整数列の特性数」、Trans. Am. Math. Soc.、33 (1): 153–165、doi : 10.1090/S0002-9947-1931-1501582-X、JSTOR  1989464
• ウォード、モーガン (1933)、「線形回帰級数の算術理論」、Trans. Am. Math. Soc.、35 (3): 600–628、doi : 10.1090/S0002-9947-1933-1501705-4、JSTOR  1989851
• ツィラー、ニール（1959）、「線形反復シーケンス」、J. SIAM、7（1）：31–38、doi：10.1137/0107003、JSTOR  2099002、MR  0101979

• mを法とするフィボナッチ数列
• フィボナッチ数列の研究
• フィボナッチ数列はq、rを法としてmで始まる
• ジョンソン、ロバート C.、フィボナッチ リソース
• フィボナッチミステリー - YouTubeの Numberphile 、ジェームズ・グライム博士とノッティンガム大学のビデオ