Número Perrin - Perrin number

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 de números de Perrin começa com

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

O número de conjuntos independentes máximos diferentes em um gráfico de ciclo de $n-$ vértices é contado pelo $n-$ ésimo número de Perrin para $n$ $> 1$ .

História

Essa sequência foi mencionada implicitamente por Édouard Lucas (1876). Em 1899, a mesma sequência foi mencionada explicitamente por François Olivier Raoul Perrin. O tratamento mais extenso dessa sequência foi dado por Adams e Shanks (1982).

Propriedades

Função geradora

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

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

Fórmula matricial

{\ displaystyle {\ begin {pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \ end {pmatrix}} ^ {n} {\ begin {pmatrix} 3 \\ 0 \\ 2 \ end {pmatrix}} = {\ begin { pmatriz} P \ esquerda (n \ direita) \\ P \ esquerda (n + 1 \ direita) \\ P \ esquerda (n + 2 \ direita) \ end {pmatriz}}}

Fórmula semelhante a Binet

Espiral de triângulos equiláteros com comprimentos laterais que seguem a sequência de Perrin.

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

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

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

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

Como as magnitudes das raízes complexas q e r são menores que 1, as potências dessas raízes se aproximam de 0 para n grande . Para n grande, a fórmula se reduz a

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

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

Fórmula de multiplicação

A partir da fórmula de Binet, podemos obter uma fórmula para G ( kn ) em termos de G ( n −1), G ( n ) e G ( n +1); nós sabemos

{\ displaystyle {\ begin {matrix} G (n-1) & = & p ^ {- 1} p ^ {n} + & q ^ {- 1} q ^ {n} + & r ^ {- 1} r ^ { n} \\ G (n) & = & p ^ {n} + & q ^ {n} + & r ^ {n} \\ G (n + 1) & = & pp ^ {n} + & qq ^ {n} + & rr ^ {n} \ end {matriz}}}

que nos dá três equações lineares com coeficientes sobre o campo de divisão de ; invertendo uma matriz que podemos resolver e então podemos elevá-los à k ésima potência e calcular a soma. ${\ displaystyle x ^ {3} -x-1}$ ${\ displaystyle p ^ {n}, q ^ {n}, r ^ {n}}$

Exemplo de código de magma :

P<x> := PolynomialRing(Rationals());
S<t> := SplittingField(x^3-x-1);
P2<y> := PolynomialRing(S);
p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]);
Mi:=Matrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1);
T<u,v,w> := 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 in [-1..1]];

com o resultado de que, se tivermos , então ${\ displaystyle u = G (n-1), v = G (n), w = G (n + 1)}$

{\ displaystyle {\ begin {matrix} 23G (2n-1) & = & 4u ^ {2} + 3v ^ {2} + 9w ^ {2} + 18uv-12uw-4vw \\ 23G (2n) & = & - 6u ^ {2} + 7v ^ {2} -2w ^ {2} -4uv + 18uw + 6vw \\ 23G (2n + 1) & = & 9u ^ {2} + v ^ {2} + 3w ^ {2} + 6uv-4uw + 14vw \\ 23G (3n-1) & = & \ left (-4u ^ {3} + 2v ^ {3} -w ^ {3} +9 (uv ^ {2} + vw ^ { 2} + wu ^ {2}) + 3v ^ {2} w + 6uvw \ direita) \\ 23G (3n) & = & \ left (3u ^ {3} + 2v ^ {3} + 3w ^ {3} -3 (uv ^ {2} + uw ^ {2} + vw ^ {2} + vu ^ {2}) + 6v ^ {2} w + 18uvw \ direita) \\ 23G (3n + 1) & = & \ left (v ^ {3} -w ^ {3} + 6uv ^ {2} + 9uw ^ {2} + 6vw ^ {2} + 9vu ^ {2} -3wu ^ {2} + 6wv ^ {2} -6uvw \ right) \ end {matrix}}}

O número 23 aqui surge do discriminante do polinômio definidor da sequência.

Isso permite o cálculo do enésimo número de Perrin usando aritmética inteira em multiplicações. ${\ displaystyle O (\ log n)}$

Primos e divisibilidade

Pseudoprimas de Perrin

Foi provado que para todos os primos p , p divide P ( p ). No entanto, o inverso não é verdadeiro: para alguns números compostos n , n ainda pode dividir P ( n ). Se n tiver esta propriedade, é denominado " pseudoprime de Perrin ".

Os primeiros pseudoprimos Perrin são

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... (sequência A013998 no OEIS )

A questão da existência de pseudoprimas de Perrin foi considerada pelo próprio Perrin, mas não se sabia se existiam até que Adams e Shanks (1982) descobriram o menor, 271441 = 521 ² ; o próximo menor é 904631 = 7 x 13 x 9941. Há dezessete deles com menos de um bilhão; Jon Grantham provou que existem infinitos pseudoprimos de Perrin.

Adams e Shanks (1982) observaram que os primos também atendem à condição de que P ( -p ) = -1 mod p . Os compostos em que ambas as propriedades são mantidas são chamados de "pseudoprimes de Perrin restritos" (sequência A018187 no OEIS ). Outras condições podem ser aplicadas usando a assinatura de seis elementos de n, que deve ser uma das três formas (por exemplo, OEIS : A275612 e OEIS : A275613 ).

Embora as pseudoprimas de Perrin sejam raras, elas têm uma sobreposição significativa com as pseudoprimas de Fermat . Isso contrasta com os pseudoprimos de Lucas, que são anticorrelacionados. A última condição é explorada para produzir o teste BPSW popular, eficiente e mais eficaz que não tem pseudoprimas conhecidas, e o menor é conhecido por ser maior que 2 ⁶⁴ .

Perrin primos

Um primo de Perrin é um número primo de Perrin . Os primeiros primos de Perrin são:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, ... (sequência A074788 no OEIS )

Para esses primos de Perrin, o índice $n$ de $P (n)$ é

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, ... (sequência A112881 no OEIS )

Gerar P (n) onde n é um número inteiro negativo produz uma propriedade semelhante em relação à primalidade: se n for negativo, então P (n) é primo quando P (n) mod -n = -n - 1. A seguinte sequência representa P (n) para todos os n que são inteiros negativos:

-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, ... (sequência A078712 no OEIS )

Notas

Referências

Füredi, Z. (1987). "O número de conjuntos independentes máximos em gráficos conectados". 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 . Addison-Wesley. ISBN 0201038048.

Leitura adicional

Adams, William; Shanks, Daniel (1982). "Testes de primalidade fortes que não são suficientes" . Matemática da Computação . American Mathematical Society. 39 (159): 255–300. doi : 10.2307 / 2007637 . JSTOR 2007637 . MR 0658231 .

Perrin, R. (1899). "Consulta 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 . The Johns Hopkins University Press. 1 (3): 197–240. doi : 10.2307 / 2369311 . JSTOR 2369311 .

links externos

Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
"Lucas Pseudoprimes" . MathPages.com .
"Sequência de Perrin" . MathPages.com .
Sequência OEIS A225876 (Composto n que divide s (n) +1, onde s é ...) - sequência semelhante a Perrina
Testes de Primalidade Perrin

Languages

In other projects