Pisanské období - Pisano period

Děj prvních 10 000 období Pisana.

v teorie čísel, nth Pisanské období, psaný π(n), je doba s nimiž sekvence z Fibonacciho čísla zaujatý modulo n opakuje. Pisanská období jsou pojmenována po Leonardovi Pisanovi, známějším jako Fibonacci. Existenci periodických funkcí v číslech Fibonacciho zaznamenal Joseph Louis Lagrange v roce 1774.^[1][2]

Definice

Čísla Fibonacci jsou čísla v celočíselná sekvence:

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, ... (sekvence A000045 v OEIS )

definováno relace opakování

${ displaystyle F_ {0} = 0}$

${ displaystyle F_ {1} = 1}$

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

Pro všechny celé číslo nposloupnost Fibonacciho čísel F_i zaujatý modulo n je periodické. Pisanské období, označené π(n), je délka období této sekvence. Například posloupnost Fibonacciho čísel modulo 3 začíná:

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, ... (sekvence A082115 v OEIS )

Tato sekvence má období 8, takže π(3) = 8.

Vlastnosti

S výjimkou π(2) = 3, období Pisano π(n) je vždy dokonce. Jednoduchý důkaz toho lze prokázat pozorováním π(n) se rovná pořadí Fibonacciho matice.

${ displaystyle mathbf {Q} = { začátek {bmatrix} 1 & 1 1 & 0 konec {bmatrix}}}$

v obecná lineární skupina GL₂(ℤ_n) z invertibilní 2 po 2 matice v konečný prsten ℤ_n z celá čísla modulo n. Od té doby Q má determinant −1, determinant Q^π(n) je (-1)^π(n), a protože to se musí rovnat 1 in ℤ_n, buď n ≤ 2 nebo π(n) je sudý.^[3]

Li m a n jsou coprime, pak π(mn) je nejmenší společný násobek z π(m) a π(n), kterou Čínská věta o zbytku. Například, π(3) = 8 a π(4) = 6 znamená π(12) = 24. Studium Pisanových období lze tedy omezit na studium Pisanových období roku hlavní síly q = p^k, pro k ≥ 1.

Li p je primární, π(p^k) rozděluje p^k–1 π(p). Není známo, zda${ displaystyle pi (p ^ {k}) = p ^ {k-1} pi (p)}$za každou premiéru p a celé číslo k > 1. Jakékoli prvočíslo p poskytující a protiklad by nutně bylo Zeď – Slunce – Slunce a naopak každý Wall – Sun – Sun Prime p dává protiklad (set k = 2).

Studium Pisanových období lze tedy dále omezit na studium Pisanových období prvočísel. V tomto ohledu jsou dvě prvočísla anomální. Prime 2 má zvláštní Pisano období a prime 5 má období, které je relativně mnohem větší než Pisano období jakéhokoli jiného prime. Období pravomocí těchto prvočísel jsou následující:

• Li n = 2^k, pak π(n) = 3·2^k–1 = 3·2^k/2 = 3n/2.
• -li n = 5^k, pak π(n) = 20·5^k–1 = 20·5^k/5 = 4n.

Z nich vyplývá, že pokud n = 2 · 5^k pak π(n) = 6n.

Zbývající prvočísla leží ve třídách zbytků ${ displaystyle p equiv pm 1 { pmod {10}}}$ nebo ${ displaystyle p equiv pm 3 { pmod {10}}}$. Li p je prvočíslo odlišné od 2 a 5, pak modulo p analog Binetův vzorec to naznačuje π(p) je multiplikativní pořadí z kořeny z X² − X − 1 modulo p. Li ${ displaystyle p equiv pm 1 { pmod {10}}}$, tyto kořeny patří ${ displaystyle mathbb {F} _ {p} = mathbb {Z} / p mathbb {Z}}$ (podle kvadratická vzájemnost ). Tak jejich pořadí, π(p) je dělitel z p - 1. Například π(11) = 11 - 1 = 10 a π(29) = (29 − 1)/2 = 14.

Li ${ displaystyle p equiv pm 3 { pmod {10}},}$ kořeny modulo p z X² − X − 1 nepatří ${ displaystyle mathbb {F} _ {p}}$ (opět kvadratickou vzájemností) a patří do konečné pole

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

Jako Frobenius automorfismus ${ displaystyle x mapsto x ^ {p}}$ vyměňuje tyto kořeny, z toho vyplývá, že je označujeme r a s, my máme r^p = s, a tudíž r^p+1 = –1. To je r^2(p+1) = 1 a období Pisano, což je řád r, je podíl 2 (p+1) lichým dělitelem. Tento kvocient je vždy násobkem 4. První příklady takového a p, pro který π(p) je menší než 2 (p+1), jsou π(47) = 2(47 + 1)/3 = 32, π(107) = 2 (107 + 1) / 3 = 72 a π(113) = 2(113 + 1)/3 = 76. (Viz tabulka níže )

Z výše uvedených výsledků vyplývá, že pokud n = p^k je lichá hlavní síla taková π(n) > n, pak π(n) / 4 je celé číslo, které není větší než n. Z toho tedy vyplývá multiplikativní vlastnost Pisanových období

π(n) ≤ 6n, s rovností právě tehdy n = 2 · 5^r, pro r ≥ 1.^[4]

První příklady jsou π(10) = 60 a π(50) = 300. Pokud n není ve formě 2 · 5^r, pak π(n) ≤ 4n.

Tabulky

Prvních dvanáct Pisanských období (sekvence A001175 v OEIS ) a jejich cykly (s mezerami pro nuly pro čitelnost) jsou^[5] (použitím hexadecimální cyphers A a B pro deset, respektive jedenáct):

Prvních 144 období Pisana je uvedeno v následující tabulce:

Pisano období Fibonacciho čísel

Li n = F(2k) (k ≥ 2), poté π (n) = 4k; -li n = F(2k + 1) (k ≥ 2), poté π (n) = 8k + 4. To znamená, že pokud je základem modulo Fibonacciho číslo (≥ 3) se sudým indexem, období je dvojnásobkem indexu a cyklus má dvě nuly. Pokud je základem Fibonacciho číslo (≥ 5) s lichým indexem, je období čtyřnásobkem indexu a cyklus má čtyři nuly.

Pisanská období Lucasových čísel

Li n = L(2k) (k ≥ 1), pak π (n) = 8k; -li n = L(2k + 1) (k ≥ 1), pak π (n) = 4k + 2. To znamená, že pokud je základem modulo Lucasovo číslo (≥ 3) s párným indexem, je období čtyřnásobkem indexu. Pokud je základem Lucasovo číslo (≥ 4) s lichým indexem, je období dvojnásobkem indexu.

Dokonce i k, cyklus má dvě nuly. Pro zvláštní k, cyklus má pouze jednu nulu a druhá polovina cyklu, která se samozřejmě rovná části nalevo od 0, se skládá ze střídavě čísel F(2m + 1) a n − F(2m), s m klesající.

Počet nul v cyklu

Tato sekce potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. (Srpna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Počet výskytů 0 na cyklus je 1, 2 nebo 4. Let p být číslo za první 0 po kombinaci 0, 1. Nechť vzdálenost mezi 0 je q.

• Je zřejmé, že v cyklu je jedna 0 p = 1. To je možné, pouze pokud q je sudý nebo n je 1 nebo 2.
• Jinak jsou v cyklu dvě 0, pokud p² ≡ 1. To je možné, pouze pokud q je sudý.
• Jinak jsou v cyklu čtyři nuly. To je případ, pokud q je liché a n není 1 nebo 2.

U zobecněných Fibonacciho sekvencí (splňujících stejný vztah opakování, ale s jinými počátečními hodnotami, např. Lucasova čísla) je počet výskytů 0 na cyklus 0, 1, 2 nebo 4.

Poměr Pisanova období roku 2006 n a počet nul modulo n v cyklu dává hodnost zjevení nebo Fibonacciho vstupní bod z n. To je nejmenší index k takhle n rozděluje F(k). Oni jsou:

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, ... ( sekvence A001177 v OEIS )

V novinách Renaultu se počet nul nazývá „řád“ F mod m, označeno ${ displaystyle omega (m)}$a „hodnost zjevení“ se nazývá „hodnost“ a označuje se ${ displaystyle alpha (m)}$.^[6]

Podle Wallova domněnky, ${ displaystyle alpha (p ^ {e}) = p ^ {e-1} alpha (p)}$. Li ${ displaystyle m}$ má Prvočíselný rozklad ${ displaystyle m = p_ {1} ^ {e_ {1}} p_ {2} ^ {e_ {2}} tečky p_ {n} ^ {e_ {n}}}$ pak ${ displaystyle alpha (m) = operatorname {lcm} ( alpha (p_ {1} ^ {e_ {1}}), alpha (p_ {2} ^ {e_ {2}}), tečky, alpha (p_ {n} ^ {e_ {n}}))}$.^[6]

Zobecnění

The Pisanská období z Pell čísla (nebo 2-Fibonacciho čísla) jsou

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, ... ( sekvence A175181 v OEIS )

The Pisanská období 3-Fibonacciho čísel jsou

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, ... ( sekvence A175182 v OEIS )

The Pisanská období z Jacobsthal čísla (nebo (1,2) -Fibonacciho čísla) jsou

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, ... ( sekvence A175286 v OEIS )

The Pisanská období z (1,3) -Fibonacciho čísel jsou

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, ... ( sekvence A175291 v OEIS )

The Pisanská období z Čísla Tribonacci (nebo 3-stupňová čísla Fibonacci) jsou

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, ... ( sekvence A046738 v OEIS )

The Pisanská období z Tetranacciho čísla (nebo čtyřstupňová čísla Fibonacci) jsou

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, ... ( sekvence A106295 v OEIS )

Viz také zobecnění Fibonacciho čísel.

Teorie čísel

Pisano období lze analyzovat pomocí algebraická teorie čísel.

Nechat ${ displaystyle pi _ {k} (n)}$ být n-th Pisano období k-Fibonacciho sekvence F_k(n) (k může být jakýkoli přirozené číslo, tyto sekvence jsou definovány jako F_k(0) = 0, F_k(1) = 1 a pro jakékoli přirozené číslo n > 1, F_k(n) = kF_k(n−1) + F_k(n−2)). Li m a n jsou coprime, pak ${ displaystyle pi _ {k} (m cdot n) = mathrm {lcm} ( pi _ {k} (m), pi _ {k} (n)),}$ podle Čínská věta o zbytku: dvě čísla jsou shodná modulo mn právě když jsou shodné modulo m a modulo n, za předpokladu, že tyto jsou coprime. Například, ${ displaystyle pi _ {1} (3) = 8}$ a ${ displaystyle pi _ {1} (4) = 6,}$ tak ${ displaystyle pi _ {1} (12 = 3 cdot 4) = mathrm {lcm} ( pi _ {1} (3), pi _ {1} (4)) = mathrm {lcm} (8,6) = 24.}$ Postačí tedy vypočítat Pisanovy periody hlavní síly ${ displaystyle q = p ^ {n}.}$ (Obvykle, ${ displaystyle pi _ {k} (p ^ {n}) = p ^ {n-1} cdot pi _ {k} (p)}$, pokud p je k-Zeď-Slunce-Slunce nebo k-Fibonacci-Wieferich prime, to znamená, p² rozděluje F_k(p - 1) nebo F_k(p + 1), kde F_k je k-Fibonacciho sekvence, například 241 je vrcholem 3-zeď-slunce-slunce, protože 241² rozděluje F₃(242).)

Pro prvočísla p, lze je analyzovat pomocí Binetův vzorec:

${ displaystyle F_ {k} left (n right) = {{ varphi _ {k} ^ {n} - (k- varphi _ {k}) ^ {n}} přes { sqrt {k ^ {2} +4}}} = {{ varphi _ {k} ^ {n} - (- 1 / varphi _ {k}) ^ {n}} přes { sqrt {k ^ {2} +4}}}, ,}$ kde ${ displaystyle varphi _ {k}}$ je kth kovový průměr

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

Li k² + 4 je a kvadratický zbytek modulo p (kde p > 2 a p nedělí k² + 4) ${ displaystyle { sqrt {k ^ {2} +4}}, 1/2,}$ a ${ displaystyle k / { sqrt {k ^ {2} +4}}}$ lze vyjádřit jako celá čísla modulo p, a tedy Binetův vzorec lze vyjádřit přes celá čísla modulo p, a tedy Pisano období rozděluje totient ${ displaystyle phi (p) = p-1}$, protože jakákoli síla (např ${ displaystyle varphi _ {k} ^ {n}}$) má dělení období ${ displaystyle phi (p),}$ protože toto je objednat z skupina jednotek modulo p.

Pro k = 1, toto poprvé nastane pro p = 11, kde 4² = 16 ≡ 5 (mod 11) a 2 · 6 = 12 ≡ 1 (mod 11) a 4 · 3 = 12 ≡ 1 (mod 11), takže 4 =√5, 6 = 1/2 a 1 /√5 = 3, poddajný φ = (1 + 4) · 6 = 30 ≡ 8 (mod 11) a shoda

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

Další příklad, který ukazuje, že období lze správně rozdělit p - 1, je π₁(29) = 14.

Li k² + 4 není kvadratický zbytek modulo p, pak je Binetův vzorec místo toho definován nad kvadratické rozšíření pole (Z/p)[√k² + 4], který má p² prvků a jejichž skupina jednotek má tedy pořádek p² - 1, a tak se období Pisana dělí p² - 1. Například pro p = 3 jeden má π₁(3) = 8, což se rovná 3² - 1 = 8; pro p = 7, jeden má π₁(7) = 16, což správně dělí 7² − 1 = 48.

Tato analýza selhala pro p = 2 a p je dělitelem části bez čtverců k² + 4, protože v těchto případech jsou nulové dělitele, takže je třeba být opatrný při interpretaci 1/2 nebo√k² + 4. Pro p = 2, k² + 4 je shodný s 1 modem 2 (pro k zvláštní), ale období Pisana není p - 1 = 1, ale spíše 3 (ve skutečnosti je to také 3 pro sudé k). Pro p rozdělí část bez čtverce k² + 4, období Pisano je π_k(k² + 4) = p² − p = p(p - 1), který se nedělí p - 1 nebo p² − 1.

Fibonacciho celočíselné sekvence modulo n

Jeden může uvažovat Fibonacciho celočíselné sekvence a vezměte je modulo n, nebo jinak řečeno, zvažte Fibonacciho sekvence v ringu Z/nZ. Období je dělitelem π (n). Počet výskytů 0 na cyklus je 0, 1, 2 nebo 4. Pokud n není prvočíslem, cykly zahrnují ty, které jsou násobky cyklů pro dělitele. Například pro n = 10 další cykly zahrnují ty pro n = 2 vynásobeno 5 a pro n = 5 vynásobeno 2.

Tabulka dalších cyklů: (původní Fibonacciho cykly jsou vyloučeny) (použití X a E pro deset, respektive 11)

Počet Fibonacciho celočíselných cyklů mod n jsou:

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, ... ( sekvence A015134 v OEIS )

Poznámky

Reference

• Bloom, D. M. (1965), „Periodicita ve zobecněných Fibonacciho sekvencích“, Amer. Matematika. Měsíční, 72 (8): 856–861, doi:10.2307/2315029, JSTOR  2315029, PAN  0222015
• Brent, Richard P. (1994), „O obdobích generalizovaných Fibonacciho sekvencí“, Matematika výpočtu, 63 (207): 389–401, arXiv:1004.5439, Bibcode:1994MaCom..63..389B, doi:10.2307/2153583, JSTOR  2153583, PAN  1216256
• Engstrom, H. T. (1931), „O sekvencích definovaných lineárními relacemi opakování“, Trans. Dopoledne. Matematika. Soc., 33 (1): 210–218, doi:10.1090 / S0002-9947-1931-1501585-5, JSTOR  1989467, PAN  1501585
• Falcon, S .; Plaza, A. (2009), "k-Fibonacciho sekvence modulo m", Chaos, solitony a fraktály, 41 (1): 497–504, Bibcode:2009CSF .... 41..497F, doi:10.1016 / j.chaos.2008.02.014
• Freyd, Peter; Brown, Kevin S. (1992), „Problémy a řešení: Řešení: E3410“, Amer. Matematika. Měsíční, 99 (3): 278–279, doi:10.2307/2325076, JSTOR  2325076
• Laxton, R. R. (1969), "O skupinách lineárních recidiv", Duke Mathematical Journal, 36 (4): 721–736, doi:10.1215 / S0012-7094-69-03687-4, PAN  0258781
• Wall, D. D. (1960), "Fibonacciho řada modulo m", Amer. Matematika. Měsíční, 67 (6): 525–532, doi:10.2307/2309169, JSTOR  2309169
• Ward, Morgan (1931), „Charakteristické číslo posloupnosti celých čísel splňujících vztah lineární rekurze“, Trans. Dopoledne. Matematika. Soc., 33 (1): 153–165, doi:10.1090 / S0002-9947-1931-1501582-X, JSTOR  1989464
• Ward, Morgan (1933), „Aritmetická teorie lineárně se opakujících řad“, Trans. Dopoledne. Matematika. Soc., 35 (3): 600–628, doi:10.1090 / S0002-9947-1933-1501705-4, JSTOR  1989851
• Zierler, Neal (1959), „Lineární opakující se sekvence“, J. SIAM, 7 (1): 31–38, doi:10.1137/0107003, JSTOR  2099002, PAN  0101979

externí odkazy

• Fibonacciho sekvence modulo m
• Výzkum Fibonacciho čísel
• Fibonacciho sekvence začíná q, r modulo m
• Johnson, Robert C., Fibonacciho zdroje
• Fibonacciho tajemství - Numberphile na Youtube, video s Dr. Jamesem Grimeem a University of Nottingham