Perrinovo číslo - Perrin number
v matematika, Perrinova čísla jsou definovány relace opakování
- P(n) = P(n − 2) + P(n − 3) pro n > 2,
s počátečními hodnotami
- P(0) = 3, P(1) = 0, P(2) = 2.
Pořadí čísel Perrin začíná na
Počet různých maximální nezávislé množiny v n-vrchol graf cyklu se počítá nčíslo Perrinu pro n > 1.[1][stránka potřebná ]
Dějiny
Tuto sekvenci implicitně zmínil Édouard Lucas (1876). V roce 1899 byla stejná sekvence výslovně zmíněna Françoisem Olivierem Raoulem Perrinem.[2][stránka potřebná ] Nejrozsáhlejší léčbu této sekvence podali Adams a Shanks (1982).
Vlastnosti
Generující funkce
The generující funkce sekvence Perrin je
Maticový vzorec
Binetový vzorec

Sekvenční čísla Perrin lze zapsat jako mocniny kořenů rovnice
Tato rovnice má 3 kořeny; jeden skutečný kořen str (známý jako plastové číslo ) a dva komplexní kořeny konjugátu q a r. Vzhledem k těmto třem kořenům je analoga Perrinovy sekvence Lucasova sekvence Binetový vzorec je
Protože velikosti komplexních kořenů q a r jsou oba menší než 1, mocniny těchto kořenů se blíží 0 pro velké n. Pro velké n vzorec se redukuje na
Tento vzorec lze použít k rychlému výpočtu hodnot Perrinovy sekvence pro velké n. Poměr po sobě jdoucích termínů v Perrinově sekvenci se blíží str, a.k.a. plastové číslo, který má hodnotu přibližně 1,324718. Tato konstanta nese stejný vztah k Perrinově sekvenci jako Zlatý řez dělá Lucasova sekvence. Podobná spojení existují také mezi str a Padovan sekvence, mezi Zlatý řez a Fibonacciho čísla a mezi poměr stříbra a Pell čísla.
Násobení vzorec
Z Binetova vzorce můžeme získat vzorec pro G(kn) ve smyslu G(n−1), G(n) a G(n+1); víme
což nám dává tři lineární rovnice s koeficienty nad rozdělení pole z ; převrácením matice, kterou můžeme vyřešit a pak je můžeme zvednout na ktu moc a spočítat součet.
Příklad magma kód:
P: = PolynomialRing (Rationals ()); S : = SplittingField (x ^ 3-x-1); P2 : = PolynomialRing (S); p, q, r: = Explode ( [r [1]: r v kořenech (y ^ 3-y-1)]); Mi: = Matrix ([[1 / p, 1 / q, 1 / r], [1,1,1], [ p, q, r]]) ^ (- 1); T : = PolynomialRing (S, 3); v1: = ChangeRing (Mi, T) * Matrix ([[u], [v ], [w]]); [p ^ i * v1 [1,1] ^ 3 + q ^ i * v1 [2,1] ^ 3 + r ^ i * v1 [3,1] ^ 3: i v [-1..1]];
s výsledkem, že pokud ano , pak
Číslo 23 zde vychází z diskriminátoru určujícího polynomu posloupnosti.
To umožňuje výpočet n-tého Perrinova čísla pomocí celočíselné aritmetiky v znásobuje.
Prvočísla a dělitelnost
Perrin pseudoprimes
Bylo prokázáno, že pro všechna prvočísla str, str rozděluje P(str). Konverzace však není pravdivá: pro některé složená čísla n, n se může stále rozdělit P(n). Li n má tuto vlastnost, nazývá se „Perrin pseudoprime ".
Prvních pár Perrin pseudoprimes je
- 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... A013998 v OEIS )
Otázku existence Perrinových pseudoprimesů zvažoval sám Perrin, ale nebylo známo, zda existují, dokud Adams a Shanks (1982) neobjevili ten nejmenší, 271441 = 5212; další nejmenší je 904631 = 7 x 13 x 9941. Je jich sedmnáct méně než miliarda;[3] Jon Grantham prokázal[4] že existuje nekonečně mnoho pseudoprimesů Perrin.
Adams and Shanks (1982) poznamenal, že prvočísla také splňují podmínku, že P(-p) = -1 mod str. Kompozity, kde obě vlastnosti drží, se nazývají "omezené Perrin pseudoprimes" (sekvence A018187 v OEIS ). Další podmínky lze použít pomocí podpisu šesti prvků n což musí být jedna ze tří forem (např. OEIS: A275612 a OEIS: A275613).
I když jsou pseudoprimesi Perrin vzácné, významně se překrývají Fermat pseudoprimes. To kontrastuje s Lucas pseudoprimes které jsou vzájemně korelované. Druhá podmínka je využívána k získání populární, efektivní a efektivnější BPSW test který nemá žádné známé pseudoprimesi a je známo, že nejmenší je větší než 264.
Perrin připraví
A Perrin Prime je Perrinovo číslo primární. Prvních několik Perrinových prvočísel je:
- 2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, ... (sekvence A074788 v OEIS )
U těchto Perrinových prvočísel index n z P(n) je
- 2, 3, 4, 5, 6, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 236, 355, 356, 930, 1042, 1214, 1461, 1622, 4430, 5802, 9092, ... (sekvence A112881 v OEIS )
Generování P (n), kde n je záporné celé číslo, poskytuje podobnou vlastnost týkající se primality: pokud n je záporné, pak P (n) je prvočíslo, když P (n) mod -n = -n - 1. Následující sekvence představuje P (n) pro všechna n, která jsou záporná celá čísla:
- -1, 1, 2, -3, 4, -2, -1, 5, -7, 6, -1, -6, 12, -13, 7, 5, -18, 25, -20, 2, 23, -43, 45, -22, -21, 66, -88, 67, -1, ... (sekvence A078712 v OEIS )
Poznámky
- ^ Füredi (1987)
- ^ Knuth (2011)
- ^ (sekvence A013998 v OEIS )
- ^ Jon Grantham (2010). „Existuje nekonečně mnoho pseudoprimesů Perrin“ (PDF). Žurnál teorie čísel. 130 (5): 1117–1128. doi:10.1016 / j.jnt.2009.11.008.
Reference
- Füredi, Z. (1987). Msgstr "Počet maximálních nezávislých množin v připojených grafech". Journal of Graph Theory. 11 (4): 463–470. doi:10.1002 / jgt.3190110403.
- Knuth, Donald E. (2011). Umění počítačového programování, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. ISBN 0201038048.
Další čtení
- Adams, William; Shanks, Daniel (1982). „Silné testy primality, které nejsou dostatečné“. Matematika výpočtu. Americká matematická společnost. 39 (159): 255–300. doi:10.2307/2007637. JSTOR 2007637. PAN 0658231.
- Perrin, R. (1899). „Dotaz 1484“. L'Intermédiaire des Mathématiciens. 6: 76.
- Lucas, E. (1878). "Théorie des fonctions numériques simplement périodiques". American Journal of Mathematics. Johns Hopkins University Press. 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311.
externí odkazy
- Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
- „Lucas Pseudoprimes“. MathPages.com.
- „Perrinova sekvence“. MathPages.com.
- OEIS posloupnost A225876 (složená n, která dělí s (n) +1, kde s je ...) - Perrinova sekvence
- Perrinovy testy primality