Número de Perrin

En matemáticas, los números de Perrin están definidos por la relación de recurrencia:

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

y

P(n) = P(n − 2) + P(n − 3) si n > 2.

La serie comienza

3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39... (sucesión A001608 en OEIS)

Considérese n para la cual n divide P(n). El resultado es

n= 1, 2, 3, 5, 7, 11, 13, ...

o sea, 1 seguido de números primos. Ha sido probado que para todos los primos p, p divide P(p).

El recíproco no es cierto. Dichos números compuestos n son llamados Pseudoprimos de Perrin, siendo el menor 271441 = 521².

Historia

La secuencia fue analizada por Édouard Lucas en 1878 (American Journal of Mathematics, vol 1, página 230ff). En 1899 la misma secuencia fue estudiada por R. Perrin (L'Intermédiaire des Mathematiciens). El estudio más largo de esta secuencia fue realizado por Dan Shanks y Bill Adams en 1982 (Mathematics of Computation, vol 39, n. 159).

Función generadora

La función generadora de la secuencia de Perrin es:

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

Matriz

Fórmula matricial de la sucesión de Perrin:

${\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}}$

Primo de Perrin

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

2, 3, 5, 7, 17, 29, 277, ....

E.W. Weisstein encontró un posible primo de Perrin de 32.147 dígitos en mayo de 2006.

Fórmulas del tipo de Binet

Consideramos las tres raíces de la ecuación polinómica siguiente:

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

Una raíz es real y dos son raíces complejas conjugadas:

${\begin{array}{l}p&=&1.324717958,\\q&=&-0.6623589786+0.5622795125i,\\r&=&-0.6623589786-0.5622795125i.\end{array}}$

Considerando estos valores, el valor de los términos de la sucesión de Perrin es el siguiente:

$P(n)=p^{n}+q^{n}+r^{n}.$

En consecuencia, el valor asintótico la sucesión de Perrin es $P(n)\approx p^{n}.$

Esta fórmula puede usarse para calcula valores de la sucesión de Perrin para un n grande. El ratio de los sucesivos términos en la sucesión de Perrin se aproxima a “p”, conocido como el número plástico, que es el valor aproximado 1.324718. Esta constante posee la misma relación con el Número de Perrin que tiene el número áureo con la sucesión de Lucas. Existen similitudes similares entre “p” y la sucesión de Padovan, entre el número áureo y la sucesión de Fibonacci y entre el ratio plateado y los números de Pell.

Fórmula de multiplicación

Podemos obtener una fórmula para G(kn) en términos de G(n-1), G(n) y G(n+1) a partir de la fórmula de Binet. Sabemos que:

${\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{matrix}}$

Que nos proporciona tres ecuaciones lineales con coeficientes sobre el cuerpo de descomposición de $x^{3}-x-1$; invirtiendo la matriz que podemos resolver con $p^{n},q^{n},r^{n}$ y después podemos elevarlos a “k” y completar la suma.

Ejemplo (Sistema algebraico computacional 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]];

Con ese resultado, si tenemos $u=G(n-1),v=G(n),w=G(n+1)$, entonces:

${\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 surge del discriminante del polinomio definitorio de la secuencia. Esto permite el cálculo de número enésimo de Perrin usando aritmética entera en multiplicaciones de $O(\log n)$ .

Primos y divisibilidad

Pseudoprimos de Perrin

Se ha probado que para todos los primos “p”, “p” divide “P”(“p”). Sin embargo, la conversión no es cierta: para algunos números compuestos “n”, “n” puede dividir aún “P”(“n”). Si “n” posee esta propiedad se le da entonces el nombre de “pseudoprimo de Perrin”.

Algunos de los primeros pseudoprimos de Perrin son

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

La existencia de los pseudoprimos de Perrin fue considerada por él mismo, pero no se supo de su existencia 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 menores al millón;​ Jon Grantham probó​ que hay infinidad de pseudoprimos de Perrin.

Adams y Shanks (1982) observaron que los primos también cumplen con la condición de que P”(“-p”)= “-1” módulo “p”. Los compuestos en los que ambas propiedades se mantienen se denominan "pseudoprimos de Perrin restringidos" (sucesión A018187 en OEIS). Se pueden aplicar condiciones adicionales usando la firma de seis elementos de n que debe ser una de tres formas (por ejemplo A275612 y A275613). Mientras que los pseudoprimos de Perrin no son frecuentes tienen una superposición significativa con el pseudoprimo de Fermat. Esto contrasta con el pseudoprimo de Lucas ya que están anti-correlacionados. Esta última condición es explotada para producir la popular, eficiente y más efectiva prueba de BPSW (Baillie-PSW_primality_test) que no tiene pseudoprimos conocidos, y la más pequeña se sabe que es mayor que 2 ⁶⁴.

Referencias

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

• 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. Addison-Wesley. ISBN 0201038048. 
• 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. JSTOR 2369311. doi:10.2307/2369311. 

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

Enlaces externos

• Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
• MathPages - Lucas Pseudoprimes
• MathPages - Perrin's Sequence
• Perrin-like sequence
• Perrin Primality Tests

• Datos: Q599093