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[editar | editar código-fonte]

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[editar | editar código-fonte]

Função geratriz[editar | editar código-fonte]

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[editar | editar código-fonte]

{\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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

[1] Füredi (1987)

[2] Knuth (2011)

[1]

[2]

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