Número de Perrin

Em matemática os números de Perrin são definidos pela relação de recorrência

P(n) = P(n − 2) + P(n − 3) para n > 2,

com valores iniciais

P(0) = 3, P(1) = 0, P(2) = 2.

A sequência dos números de Perrin começa com

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, ... (sequência A001608 na OEIS)

O número de diferentes conjuntos independentes máximos em um n-vértice grafo ciclo é contado pelo n-ésimo número de Perrin para n > 1.^[1]

História

Esta sequência foi mencionada implicitamente por Édouard Lucas (1876). Em 1899 e mesma sequência foi mencionada explicitamente por Raoul Perrin.^[2] O mais extensivo tratamento desta sequência foi dado por Adams e Shanks (1982).

Propriedades

Função geratriz

A função geratriz da sequência de Perrin é

G(P(n);x)={\frac {3-x^{2}}{1-x^{2}-x^{3}}}.

Fórmula matricial

{\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P\left(n\right)\\P\left(n+1\right)\\P\left(n+2\right)\end{pmatrix}}

Fórmula tipo Binet

Os números da sequência de Perrin podem ser escritos em termos das potências das raízes da equação

x^{3}-x-1=0.

esta equação tem 3 rraízes; uma raiz real p (conhecida como número plástico) e duas raízes complexas conjugadas q e r. dadas estas três raízes, a sequência de Perrin análoga à fórmula de Binet da sequência de Lucas é

P\left(n\right)={p^{n}}+{q^{n}}+{r^{n}}.

Como as magnitudes das raízes complexas q e r são ambas menores que 1, as potências destas raízes convergem para 0 para n grande, e a fórmula se reduz a

P\left(n\right)\approx {p^{n}}.

esta fórmula pode ser usada para calcular rapidamente valores da sequência de Perrin para n grande. A razão de termos sucessivos na sequência de Perrin se aproxima de p, também conhecido como número plástico, que tem um valor de aproximadamente 1,324718. esta constante tem a mesma relação com a sequência de Perrin como acontece com a proporção áurea em relação à sequência de Lucas. Conexões similares também exestem entre p e a sequência de Padovan, entre a proporção áurea e os números de Fibonacci, e entre a proporção prateada e os números de Pell.

Bibliografia

Füredi, Z. (1987). «The number of maximal independent sets in connected graphs». Journal of Graph Theory. 11 (4): 463–470. doi:10.1002/jgt.3190110403

Knuth, Donald E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. [S.l.]: Addison-Wesley. ISBN 0201038048

Leitura adicional

Adams, William; Shanks, Daniel (1982). «Strong primality tests that are not sufficient». American Mathematical Society. Mathematics of Computation. 39 (159): 255–300. JSTOR 2007637. MR 0658231. doi:10.2307/2007637

Perrin, R. (1899). «Query 1484». L'Intermédiaire des Mathématiciens. 6. 76 páginas

Lucas, E. (1878). «Théorie des fonctions numériques simplement périodiques». The Johns Hopkins University Press. American Journal of Mathematics. 1 (3): 197–240. JSTOR 2369311. doi:10.2307/2369311

Ligações externas

Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
Perrin Primality Tests

v d e Classes de números primos
Por fórmula	Fermat $(2^{2^{n}}+1)$ Mersenne $(2^{p}-1)$ Duplo de Mersenne $(2^{2^{p}-1}-1)$ Wagstaff ${\frac {(2^{p}+1)}{3}}$ Proth $(k\cdot 2^{n}+1)$ Factorial $(n!\pm 1)$ Primorial $(p_{n}\#\pm 1)$ Euclides $(p_{n}\#+1)$ Pitagórico $(4n+1)$ Pierpont $(2^{u}\cdot 3^{v}+1)$ Solinas $(2^{a}\pm 2^{b}\pm 1)$ Cullen $(n\cdot 2^{n}+1)$ Woodall $(n\cdot 2^{n}-1)$ Cubano ${\frac {(x^{3}-y^{3})}{(x-y)}}$ Carol ${(2^{n}-1)}^{2}-2$ Kynea ${(2^{n}+1)}^{2}-2$ Leyland $(x^{y}+y^{x})$ Thabit $(3\cdot 2^{n}-1)$ Mills (chão $(A^{3^{n}})$ )
Por sequência de inteiros	Fibonacci Lucas Motzkin Bell Partições Pell Perrin Newman–Shanks–Williams
Por propriedade	Da sorte Wall–Sun–Sun Wilson Wieferich Par de Wieferich Afortunado Ramanujan Pillai Regular Forte Stern Supersingular Wolstenholme Bom Superprimo Higgs Altamente cototiente Ilegal
Dependentes de bases	Feliz Diédrico Palíndromo Omirp Repunit ${\frac {(10^{n}-1)}{9}}$ Permutável Circular Estrobogramático Mínimo Longo único Primeval Auto Smarandache–Wellin
Padrões	Gémeos $(p,p+2)$ Tripla $(p,p+2~ou~p+4,p+6)$ Quádrupla $(p,p+2,p+6,p+8)$ Tuplo Primos primos $(p,p+4)$ Sexy $(p,p+6)$ Chen Sophie Germain $(p,2p+1)$ Cadeia de Cunningham $(p,2p\pm 1,\ldots )$ Seguro $(p,{\frac {(p-1)}{2}})$ Progressão aritmética $(p+a\cdot n,n=0,1,\ldots )$ Equilibrado (consecutivos $p-n,p,p+n)$
Por dimensão	Titânico ( $1000+$ dígitos) Gigantesco ( $10000+$ ) Megaprimo ( $1000000+$ ) Maior conhecido
Números complexos	Eisenstein Gauss
Números compostos	Número pseudoprimo Quase primo Semiprimo Interprimo
Tópicos relacionados	Provável Nível industrial Fórmula para números primos Intervalo entre números primos consecutivos
Lista de números primos

Classes de números naturais

Potências e números relacionados

Aquiles
Potência de 2
Potência de 10
Quadrado
Cubo
Quarta potência
Quinta potência
Potência perfeita
Potente
Potência prima

Da forma a × 2^b ± 1

Outros números polinomiais

Carol
Hilbert
Idôneo
Kynea
Leyland
Números da sorte de Euler
Repunit

Números definidos recursivamente

Possuindo um conjunto específico
de outros números

Knödel
Riesel
Sierpiński

Expressáveis via somas específicas

Não-hipotenusa
Polido
Prático
Primário pseudoperfeito
Ulam
Wolstenholme

Gerado via uma teoria dos crivos

Sorte

Relacionado a codificação

Meertens

Números figurados

centrado	Triangular centrado Quadrado centrado Pentagonal centrado Hexagonal centrado Heptagonal centrado Octagonal centrado Nonagonal centrado Decagonal centrado Estrela
não-centrado	Triangular quadrado Quadrado triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

centrado	Tetraédrico centrado Cúbico centrado Octaédrico centrado Dodecaédrico centrado Icosaédrico centrado
Não-centrado	Tetraédrico Octaédrico Dodecaédrico Icosaédrico Stella octangula
Piramidal	Piramidal quadrado Piramidal pentagonal Piramidal hexagonal Piramidal heptagonal

centrado	Pentácoro centrado Triangular quadrado
Não-centrado	Pentácoro

Pseudoprimos

Número de Carmichael
Pseudoprimo de Catalan
Pseudoprimo elíptico
Pseudoprimo de Euler
Pseudoprimo de Euler–Jacobi
Pseudoprimo de Fermat
Pseudoprimo de Frobenius
Pseudoprimo de Lucas
Pseudoprimo de Somer–Lucas
Pseudoprimo forte

Números combinatoriais

Bell
Bolo
Catalan
Dedekind
Delannoy
Euler
Fuss–Catalan
Número poligonal central
Lobb
Motzkin
Narayana
Ordenado de Bell
Schröder
Schröder–Hipparchus

Funções aritméticas

Por propriedades de σ(n)	Abundante Quase perfeito Aritmético Colossalmente abundante Descartes Hemiperfeito Altamente abundante Altamente composto Hyperperfeito Multiplamente perfeito Perfeito Número prático Primitivo abundante Quase perfeito Refactorável Sublime Superabundante Superior altamente composto Superperfeito
Por propriedades de Ω(n)	Quasi-primo Semiprimo
Por propriedades de φ(n)	Altamente cototiente Altamente totiente Não-cototiente Não-totiente Perfeito totiente Esparsamente totiente
Por propriedades de s(n)	Amigo Quasi-amigo Defectivo Semiperfeito