Número de Perrin

En matemáticas , los números de Perrin se definen por la relación de recurrencia

P (n) = P (n - 2) + P (n - 3)

para

n > 2

,

con valores iniciales

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

.

La secuencia de números de Perrin comienza con

3 , 0 , 2 , 3, 2, 5 , 5, 7 , 10 , 12 , 17 , 22 , 29 , 39 , ... (secuencia A001608 en la OEIS )

El número de conjuntos independientes máximos diferentes en un gráfico de ciclo de $n$ - vértices se cuenta por el número $n-$ ésimo de Perrin para $n > 1$ . ^[1]^{[ página necesaria ]}

Historia

Esta secuencia fue mencionada implícitamente por Édouard Lucas (1876). En 1899, François Olivier Raoul Perrin mencionó explícitamente la misma secuencia. ^[2]^{[ página necesaria ]} Adams y Shanks (1982) dieron el tratamiento más extenso de esta secuencia.

Propiedades

Función generadora

La función generadora de la secuencia de Perrin es

{\ 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 { pmatrix} P \ left (n \ right) \\ P \ left (n + 1 \ right) \\ P \ left (n + 2 \ right) \ end {pmatrix}}}

Fórmula similar a Binet

Espiral de triángulos equiláteros con longitudes de lados que siguen la secuencia de Perrin.

Los números de secuencia de Perrin se pueden escribir en términos de potencias de las raíces de la ecuación

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

Esta ecuación tiene 3 raíces; una raíz real p (conocido como el número de plástico ) y dos raíces complejas conjugadas q y r . Dadas estas tres raíces, el análogo de la secuencia de Perrin de la fórmula de Binet de la secuencia de Lucas es

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

Dado que las magnitudes de las raíces complejo q y r están a menos de 1, los poderes de estas raíces se acercan a 0 para grandes n . Para n grandes, la fórmula se reduce a

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

Esta fórmula se puede utilizar para calcular rápidamente los valores de la secuencia de Perrin para n grandes. La proporción de términos sucesivos en la secuencia de Perrin se aproxima a p , también conocido como número plástico , que tiene un valor de aproximadamente 1,324718. Esta constante tiene la misma relación con la secuencia de Perrin que la proporción áurea con la secuencia de Lucas . También existen conexiones similares entre py la secuencia de Padovan , entre la proporción áurea y los números de Fibonacci, y entre la proporción de plata y los números de Pell .

Fórmula de multiplicación

De la fórmula de Binet, podemos obtener una fórmula para G ( kn ) en términos de G ( n −1), G ( n ) y G ( n +1); 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}}}

lo que nos da tres ecuaciones lineales con coeficientes sobre el campo de división de ; invirtiendo una matriz que podemos resolver y luego podemos elevarlos a la k- ésima potencia y calcular la suma. ${\ Displaystyle x ^ {3} -x-1}$ ${\ Displaystyle p ^ {n}, q ^ {n}, r ^ {n}}$

Ejemplo de código de magma :

P <x>: = PolynomialRing (Racionales ());
S <t>: = campo de división (x ^ 3-x-1);
P2 <y>: = PolynomialRing (S);
p, q, r: = Explotar ([r [1]: r en Raíces (y ^ 3-y-1)]);
Mi: = Matriz ([[1 / p, 1 / q, 1 / r], [1,1,1], [p, q, r]]) ^ (- 1);
T <u, v, w>: = PolynomialRing (S, 3);
v1: = ChangeRing (Mi, T) * Matriz ([[u], [v], [w]]);
[p ^ i * v1 [1,1] ^ 3 + q ^ i * v1 [2,1] ^ 3 + r ^ i * v1 [3,1] ^ 3: i en [-1..1]] ;

con el resultado de que, si tenemos , entonces $u=G(n-1),v=G(n),w=G(n+1)$

{\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\right)\\23G(3n)&=&\left(3u^{3}+2v^{3}+3w^{3}-3(uv^{2}+uw^{2}+vw^{2}+vu^{2})+6v^{2}w+18uvw\right)\\23G(3n+1)&=&\left(v^{3}-w^{3}+6uv^{2}+9uw^{2}+6vw^{2}+9vu^{2}-3wu^{2}+6wv^{2}-6uvw\right)\end{matrix}}

El número 23 aquí surge del discriminante del polinomio definitorio de la secuencia.

Esto permite el cálculo del n-ésimo número de Perrin usando aritmética de enteros en multiplicaciones. $O(\log n)$

Primas y divisibilidad

Pseudoprimes de Perrin

Se ha demostrado que para todos los primos p , p divide a P ( p ). Sin embargo, lo contrario no es cierto: para algunos números compuestos n , n aún puede dividir P ( n ). Si n tiene esta propiedad, se denomina " pseudoprime de Perrin ".

Los primeros pseudoprimes de Perrin son

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... (secuencia A013998 en la OEIS )

La cuestión de la existencia de los pseudoprimos de Perrin fue considerada por el propio Perrin, pero no se supo si existían hasta que Adams y Shanks (1982) descubrieron el más pequeño, 271441 = 521 ² ; el siguiente más pequeño es 904631 = 7 x 13 x 9941. Hay diecisiete de ellos menos de mil millones; ^[3] Jon Grantham ha demostrado ^[4] que hay infinitos pseudoprimes de Perrin.

Adams y Shanks (1982) observaron que los números primos también cumplen la condición de que P ( -p ) = -1 mod p . Los compuestos en los que se mantienen ambas propiedades se denominan "pseudoprimes de Perrin restringidos" (secuencia A018187 en la OEIS ). Se pueden aplicar más condiciones utilizando la firma de seis elementos de n, que debe ser una de tres formas (por ejemplo, OEIS : A275612 y OEIS : A275613 ).

Si bien los pseudoprimes de Perrin son raros, tienen una superposición significativa con los pseudoprimes de Fermat . Esto contrasta con los pseudoprimos de Lucas que están anti-correlacionados. La última condición se explota para producir la prueba BPSW popular, eficiente y más efectiva que no tiene pseudoprimes conocidos, y se sabe que la más pequeña es mayor que 2 ⁶⁴ .

Perrin primos

Un número primo de Perrin es un número de Perrin que es primo . Los primeros números primos de Perrin son:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071579864797, ... (secuencia A074788 en la OEIS )

Para estos números primos de Perrin, el índice $n$ de $P (n)$ es

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, ... (secuencia A112881 en la OEIS )

Generar P (n) donde n es un número entero negativo produce una propiedad similar con respecto a la primalidad: si n es negativo, entonces P (n) es primo cuando P (n) mod -n = -n - 1. La siguiente secuencia representa P (n) para todos los n que son enteros 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, ... (secuencia A078712 en la OEIS )

Notas

^ Füredi (1987)
^ Knuth (2011)
^ (secuencia A013998 en la OEIS )
^ Jon Grantham (2010). "Hay una infinidad de pseudoprimes de Perrin" (PDF) . Revista de teoría de números . 130 (5): 1117–1128. arXiv : 1903.06825 . doi : 10.1016 / j.jnt.2009.11.008 .

Referencias

Füredi, Z. (1987). "El número de conjuntos independientes máximos en gráficos conectados". Revista de teoría de grafos . 11 (4): 463–470. doi : 10.1002 / jgt.3190110403 .

Knuth, Donald E. (2011). El arte de la programación informática , volumen 4A: algoritmos combinatorios, parte 1 . Addison-Wesley. ISBN 0201038048.

Otras lecturas

Adams, William; Shanks, Daniel (1982). "Pruebas de primordialidad fuertes que no son suficientes" . Matemáticas de la Computación . Sociedad Matemática Estadounidense. 39 (159): 255–300. doi : 10.2307 / 2007637 . JSTOR 2007637 . Señor 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". Revista Estadounidense de Matemáticas . Prensa de la Universidad Johns Hopkins. 1 (3): 197–240. doi : 10.2307 / 2369311 . JSTOR 2369311 .

enlaces externos

Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
"Lucas Pseudoprimes" . MathPages.com .
"Secuencia de Perrin" . MathPages.com .
Secuencia OEIS A225876 (Compuesto n que divide s (n) +1, donde s es ...) —Secuencia similar a la de la perrina
Pruebas de primordialidad de Perrin

[1] Füredi (1987)

[2] Knuth (2011)

[3] (secuencia A013998 en la OEIS )

[4] Jon Grantham (2010). "Hay una infinidad de pseudoprimes de Perrin" (PDF) . Revista de teoría de números . 130 (5): 1117–1128. arXiv : 1903.06825 . doi : 10.1016 / j.jnt.2009.11.008 .

[1]