Número de Perrin

En matemáticas, los números de Perrin son una secuencia de enteros $recursiva$ constante doblemente infinita con ecuación característica $x³$ $=$ $x$ $+ 1.$ Los números de Perrin, que reciben su nombre del ingeniero francés Raoul Perrin , guardan la misma relación con la secuencia de Padovan que los números de Lucas con la secuencia de Fibonacci .

Definición

Los números de Perrin se definen mediante la relación de recurrencia.

{\begin{aligned}P(0)&=3,\\P(1)&=0,\\P(2)&=2,\\P(n)&=P(n-2)+P(n-3){\mbox{ para }}n>2,\end{aligned}}

y lo contrario

P(n)=P(n+3)-P(n+1){\mbox{ para }}n<0.

Los primeros términos en ambas direcciones son

Los números de Perrin se pueden expresar como sumas de los tres términos iniciales.

{\begin{array}{c|c|c}n&P(n)&P(-n)\\\hline 0&P(0)&...\\1&P(1)&P(2)-P(0)\\2&P(2)&-P(2)+P(1)+P(0)\\3&P(1)+P(0)&P(2)-P(1)\\4&P(2)+P(1)&P(1)-P(0)\\5&P(2)+P(1)+P(0)&-P(2)+2P(0)\\6&P(2)+2P(1)+P(0)&2P(2)-P(1)-2P(0)\\7&2P(2)+2P(1)+P(0)&-2P(2)+2P(1)+P(0)\\8&2P(2)+3P(1)+2P(0)&P(2)-2P(1)+P(0)\end{array}}

Los primeros catorce números primos de Perrin son

Historia

En 1876, Édouard Lucas mencionó por primera vez la secuencia y su ecuación , señalando que el índice n divide al término $P(n)$ si n es primo. ^{[ 5 ]} En 1899, Raoul Perrin preguntó si existían contraejemplos a esta propiedad. ^{[ 6 ]} El primer $P(n)$ divisible por un índice compuesto n fue hallado recién en 1982 por William Adams y Daniel Shanks . ^{[ 7 ]} Presentaron una investigación detallada de la secuencia, con una continuación que apareció cuatro años después. ^{[ 8 ]}

Propiedades

La secuencia de Perrin también satisface la relación de recurrencia. $P(n)=P(n-1)+P(n-5).$ Partiendo de esto y de la recurrencia definitoria, se puede crear un número infinito de relaciones adicionales, por ejemplo $P(n)=P(n-3)+P(n-4)+P(n-5).$

La función generadora de la secuencia de Perrin es

{\frac {3-x^{2}}{1-x^{2}-x^{3}}}=\sum _{n=0}^{\infty }P(n)\,x^{n}

La secuencia está relacionada con sumas de coeficientes binomiales por

P(n)=n\times \sum _{k=\lfloor (n+2)/3\rfloor }^{\lfloor n/2\rfloor }{\binom {k}{n-2k}}/k,

^{[ 1 ]}

$P(-n)=n\times \sum _{k=0}^{\lfloor n/3\rfloor }(-1)^{nk}{\binom {n-2k}{k}}/(n-2k).$

Los números de Perrin se pueden expresar en términos de sumas parciales.

{\begin{aligned}P(n+5)-2&=\sum _{k=0}^{n}P(k)\\P(2n+3)&=\sum _{k=0}^{n}P(2k)\\5-P(4-n)&=\sum _{k=0}^{n}P(-k)\\3-P(1-2n)&=\sum _{k=0}^{n}P(-2k).\end{alineado}}

Los números de Perrin se obtienen como potencias enteras $n \geq 0$ de la matriz.

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

y su inversa

{\begin{pmatrix}-1&0&1\\1&0&0\\0&1&0\end{pmatrix}}^{n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P(-n)\\P(1-n)\\P(2-n)\end{pmatrix}}.

El análogo de Perrin de la identidad de Simson para los números de Fibonacci viene dado por el determinante

{\begin{vmatrix}P(n+2)&P(n+1)&P(n)\\P(n+1)&P(n)&P(n-1)\\P(n)&P(n-1)&P(n-2)\end{vmatrix}}=-23.

El número de conjuntos independientes máximos diferentes en un grafo cíclico de n vértices se cuenta mediante el n -ésimo número de Perrin para $n \geq$ 2. ^[⁹^]

Fórmula de Binet

La solución de la recurrencia $P(n)=P(n-2)+P(n-3)$ puede escribirse en términos de las raíces de la ecuación característica $x^{3}-x-1=0$ . Si las tres soluciones son raíces reales $\alpha$ ( con un valor aproximado de 1,324718 y conocido como la relación plástica ) yraíces conjugadas complejas . $\beta$ y $\gamma$ Los números de Perrin se pueden calcular con la fórmula de Binet . $P(n)=\alpha ^{n}+\beta ^{n}+\gamma ^{n},$ lo cual también es válido para n negativo .

La forma polar es $P(n)=\alpha ^{n}+2\cos(n\,\theta ){\sqrt {\alpha ^{-n}}},$ con $\theta =\arccos(-{\sqrt {\alpha ^{3}}}/2).$ Desde $\lim _{n\to \infty }\alpha ^{-n}=0,$ La fórmula se reduce sucesivamente al primer o al segundo término para valores grandes de n positivos o negativos , y los números con subíndices negativos oscilan. Siempre que α se calcule con la precisión suficiente, estas fórmulas pueden utilizarse para calcular los números de Perrin para valores grandes de n .

Ampliando la identidad $P^{2}(n)=(\alpha ^{n}+\beta ^{n}+\gamma ^{n})^{2}$ proporciona la importante regla de duplicación de índices $P(2n)=P^{2}(n)-2P(-n),$ mediante la cual se enlazan las partes directa e inversa de la secuencia.

El índice primo p divide a P(p).

Si la ecuación característica de la secuencia se escribe como $f(x)=x^{3}-\sigma _{1}x^{2}+\sigma _{2}x-\sigma _{3}$ luego los coeficientes $\sigma _{k}$ puede expresarse en términos de raíces $\alpha ,\beta ,\gamma$ con las fórmulas de Vieta :

{\begin{alignedat}{3}\sigma _{1}&=\alpha +\beta +\gamma &&=0\\\sigma _{2}&=\alpha \beta +\alpha \gamma +\beta \gamma &&=-1\\\sigma _{3}&=\alpha \beta \gamma &&=1.\end{alignedat}}

Estas funciones de valor entero son los polinomios simétricos elementales en $\alpha ,\beta ,\gamma .$

El teorema fundamental sobre polinomios simétricos establece que todo polinomio simétrico en las raíces complejas de mónicos ⁠ $f$ ⁠ puede representarse como otra función polinómica en los coeficientes enteros de ⁠ $f.$ ⁠
El análogo del teorema de Lucas para coeficientes multinomiales ${\frac {p!}{i!j!k!}}$ dice que si $i,j,k<p$ entonces ${\binom {p}{i,j,k}}$ es divisible por primo $p.$ ⁠

Dados los números enteros $a,b,c$ y $n>0,$ ⁠

(a+b+c)^{n}=\sum _{i+j+k=n}{\binom {n}{i,j,k}}a^{i}b^{j}c^{k}.

Reorganizar en sumandos monomiales simétricos , permutando los exponentes $i, j, k:$

(a+b+c)^{n}-(a^{n}+b^{n}+c^{n})=

\sum _{\begin{aligned}i\leq j\leq k&<n\\i+j+k&=n\end{aligned}}{\binom {n}{i,j,k}}\sum _{\pi (i,j,k)}a^{i}b^{j}c^{k}.

Sustituir primo $p$ para obtener energía $n$ y raíces complejas $\alpha ,\beta ,\gamma$ para números enteros $a,b,c$ y calcular representaciones en términos de $\sigma _{1},\sigma _{2},\sigma _{3}$ para todas las funciones polinómicas simétricas. Por ejemplo, $(\alpha +\beta +\gamma )^{p}$ es $\sigma _{1}^{p}=0$ y la suma de potencias $\alpha ^{p}+\beta ^{p}+\gamma ^{p}=P(p)$ puede expresarse en los coeficientes $\sigma _{k}$ Con el esquema recursivo de Newton . Deello se deduce que la identidad tiene términos enteros y ambos lados son divisibles por números primos . $p.$ ⁠

Para demostrar que es primo $p$ divide $P(-p)+1$ En la secuencia inversa, la ecuación característica debe reflejarse . Las raíces son entonces $\alpha ^{-1},\beta ^{-1},\gamma ^{-1},$ los coeficientes $\sigma _{1}=-1,\sigma _{2}=0,\sigma _{3}=1,$ y se aplica el mismo razonamiento.

Prueba de primacía de Perrin

Consulta 1484. La curiosa proposición de origen chino que es objeto de la consulta 1401 ^{[ 10 ]} proporcionaría, si es cierta, un criterio más práctico que el teorema de Wilson para verificar si un número dado $m$ es primo o no; bastaría con calcular los residuos con respecto a $m$ de términos sucesivos de la secuencia de recurrencia $u n = 3 u n-1 - 2 u n-2$ con valores iniciales $u 0 =-1, u 1 = 0.$ ^{[ 11 ]} He encontrado otra secuencia de recurrencia que parece poseer la misma propiedad; es aquella cuyo término general es $v n = v n-2 + v n-3$ con valores iniciales $v 0 = 3, v 1 = 0, v 2 = 2.$ Es fácil demostrar que $v n$ es divisible por $n$ , si $n$ es primo; He comprobado, hasta valores bastante altos de $n$ , que en el caso contrario no es así; pero sería interesante saber si esto es realmente cierto, especialmente porque la secuencia $v n$ produce números que aumentan mucho menos rápidamente que la secuencia $u n$ (para $n = 17$ , por ejemplo, se encuentra $u n = 131070, v n = 119$ ), lo que lleva a cálculos más sencillos cuando $n$ es un número grande. La misma demostración, aplicable a una de las secuencias, sin duda tendrá relación con la otra, si la propiedad enunciada es cierta para ambas: es solo cuestión de descubrirla. ^{[ 12 ]}

La secuencia de Perrin tiene la propiedad de Fermat : si $p$ es primo , ${\textstyle P(p)\equiv P(1)\equiv 0{\pmod {p}}.}$ Sin embargo, lo contrario no es cierto: algún compuesto $n$ aún puede dividirse $P(n).$ Un número con esta propiedad se denomina pseudoprimo de Perrin .

La cuestión de la existencia de pseudoprimos de Perrin fue considerada por Malo y Jarden, ^{[ 13 ]} pero no se conocía ninguno hasta que Adams y Shanks encontraron el más pequeño, $271441=521^{2}$ (el número $P(271441)$ tiene 33150 dígitos decimales). ^{[ 14 ]} Jon Grantham demostró posteriormente que existen infinitos pseudoprimos de Perrin. ^{[ 15 ]}

Los diecisiete pseudoprimos de Perrin menores que $10⁹$ $son$ 271441 , 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431. ^{[ 16 ]}

Adams y Shanks observaron que los números primos también satisfacen la congruencia. ${\textstyle P(-p)\equiv P(-1)\equiv -1{\pmod {p}}.}$ Los números compuestos que cumplen ambas propiedades se denominan pseudoprimos de Perrin restringidos. Solo existen nueve números de este tipo menores $que$ $10⁹$ . ^{[ 17 ]}^{[ 18 ]}^{[ 19 ]}

Si bien los pseudoprimos de Perrin son raros, se superponen con los pseudoprimos de Fermat . De los diecisiete números mencionados, cuatro también son fermatianos de base $2. En cambio, los$ pseudoprimos de Lucas están anticorrelacionados. ^{[ 20 ]} Presumiblemente, combinar las pruebas de Perrin y Lucas debería dar como resultado una prueba de primalidad tan sólida como la prueba BPSW , que no tiene pseudoprimos conocidos, aunque con un mayor costo computacional.

Pseudocódigo

Adams y Shanks de 1982 $O(\log n)$ Prueba de primalidad de Perrin. ^{[ 21 ]}

Dos matrices enteras u(3) y v(3) se inicializan con los términos más bajos de la secuencia de Perrin, con índices positivos $t = 0, 1, 2$ en u( ) e índices negativos $t = 0,-1,-2$ en v( ).

El bucle principal de duplicación y suma , diseñado originalmente para ejecutarse en una calculadora de bolsillo HP-41C , calcula $P(n) mod n$ y el inverso $P(-n) mod n$ a costa de seis elevaciones al cuadrado modulares por cada bit de $n$ .

Los subíndices de los números de Perrin se duplican usando la identidad $P(2t) = P 2 (t) - 2P(-t)$ . Las brechas resultantes entre $P(\pm2t)$ y $P(\pm2t \pm 2)$ se cierran aplicando la relación definitoria $P(t) = P(t - 2) + P(t - 3)$ .

Valores iniciales : sea int u(0):= 3, u(1):= 0, u(2):= 2; sea int v(0):= 3, v(1):=−1, v(2):= 1Prueba de número positivo impar n entrada int n establecer int h:= bit más significativo de n para k:= h − 1 hasta 0 Duplica los índices de los seis números de Perrin. para i = 0, 1, 2 temp:= u(i)^2 − 2v(i) (mod n) v(i):= v(i)^2 − 2u(i) (mod n) u(i):= temp fin paraCopia P(2t + 2) y P(−2t − 2) a los extremos del arreglo y úsalos en la instrucción if a continuación. u(3):= u(2) v(3):= v(2) Sobrescribe P(2t ± 2) con P(2t ± 1) temp:= u(2) − u(1) u(2):= u(0) + temp u(0):= temp Sobrescribe P(−2t ± 2) con P(−2t ± 1) temp:= v(0) − v(1) v(0):= v(2) + temp v(2):= temp Si n tiene el bit k activado, entonces aumenta en 1 los índices de ambas ternas de Perrin. Para i = 0, 1, 2 u(i):= u(i + 1) v(i):= v(i + 1) fin para fin sifin paraResultado imprimir v(2), v(1), v(0) imprimir u(0), u(1), u(2)

Sucesivamente $P(-n - 1), P(-n), P(-n + 1)$ y $P(n - 1), P(n), P(n + 1) (mod n)$ .

Si $P(-n) = -1$ y $P(n) = 0$ entonces n es un primo probable , es decir: realmente primo o un pseudoprimo de Perrin restringido.

Shanks et al. observaron que para todos los pseudoprimos restringidos que encontraron, el estado final de los seis registros anteriores (la "firma" de n ) es igual al estado inicial 1,−1,3, 3,0,2. ^{[ 22 ]} Lo mismo ocurre con $\approx 1 / 6$ de todos los primos, por lo que los dos conjuntos no se pueden distinguir basándose únicamente en esta prueba. ^{[ 23 ]} Para esos casos, recomiendan utilizar también la secuencia hermana de Narayana-Lucas con relación de recurrencia $A(n) = A(n - 1) + A(n - 3)$ y valores iniciales

u(0):= 3, u(1):= 1, u(2):= 1 v(0):= 3, v(1):= 0, v(2):=−2

Se aplica la misma regla de duplicación y las fórmulas para rellenar los huecos son:

temp:= u(0) + u(1) u(0):= u(2) − temp u(2):= temp temp:= v(2) + v(1) v(2):= v(0) − temp v(0):= temp

Aquí, n es un primo probable si $A(-n) = 0$ y $A(n) = 1$ .

Kurtz et al. no encontraron superposición entre los pseudoprimos impares para las dos secuencias por debajo de $50∙10 9$ y supusieron que 2,277,740,968,903 = 1067179 ∙ 2134357 es el número compuesto más pequeño que pasa ambas pruebas. ^{[ 24 ]}

Si también se utiliza la recurrencia de Pell-Lucas de tercer orden $A(n) = 2A(n - 1) + A(n - 3)$ , este límite se extenderá hasta 4.057.052.731.496.380.171 = 1424263447 ∙ 2848526893. ^{[ 25 ]}

Además, raíces de la regla de duplicación-congruencia $x^{2}-2x\equiv 3=P(0){\pmod {n}}\,$ other than $-1$ or $3$ expose composite numbers, like non-trivial square roots of $1$ in the Miller-Rabin test.^[26] This reduces the number of restricted pseudoprimes for each sequence by roughly one-third and is especially efficient in detecting Carmichael numbers.^[27]

The least strong restricted Perrin pseudoprime is 46672291 and the above two bounds expand to successively 173,536,465,910,671 and 79,720,990,309,209,574,421.^[28]

Notes

1 2Sloane, N. J. A. (ed.). "SequenceA001608(Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3) with a(0) = 3, a(1) = 0, a(2) = 2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
↑Sloane, N. J. A. (ed.). "SequenceA078712(Series expansion of (-3 - 2*x)/(1 + x - x^3) in powers of x)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
↑Sloane, N. J. A. (ed.). "SequenceA112881(Indices of prime Perrin numbers; values of n such that A001608(n) is prime)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
↑Sloane, N. J. A. (ed.). "SequenceA074788(Prime numbers in the Perrin sequence b(n+1) = b(n-1) + b(n-2) with initial values b(1)=3, b(2)=0, b(3)=2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
↑Lucas (1878)
↑Perrin (1899)
↑Adams & Shanks (1982)
↑Kurtz, Shanks & Williams (1986)
↑Füredi (1987)
↑Tarry (1898)
↑Sloane, N. J. A. (ed.). "SequenceA000918(a(n) = 2^n − 2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
↑Perrin (1899) translated from the French
↑Malo (1900), Jarden (1966)
↑Adams & Shanks (1982, p. 255)
↑Grantham (2010), Stephan (2020)
↑ Sloane, N. J. A. (ed.). "Secuencia A013998 (pseudoprimos de Perrin sin restricciones)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
↑ Sloane, N. J. A. (ed.). "Secuencia A018187 (pseudoprimos de Perrin restringidos)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
↑ Sloane, N. J. A. (ed.). "Secuencia A275612 (pseudoprimos de Perrin restringidos (definición de Adams y Shanks))" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
↑ Sloane, N. J. A. (ed.). "Secuencia A275613 (Pseudoprimos de Perrin restringidos (definición de Grantham))" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
↑ Ninguno de los 2402549 pseudoprimos de Lucas-Selfridge por debajo de $1015$ enumerados por Dana Jacobsen (2020) es también un pseudoprimo de Perrin.
↑ Adams y Shanks (1982 , págs. 265, 269-270)
↑ Adams y Shanks (1982 , pág. 275) , Kurtz, Shanks y Williams (1986 , pág. 694) . Esto fue confirmado posteriormente para $n < 10$ $14$ por Steven Arno (1991) .
↑ La firma sí proporciona información discriminatoria sobre los dos tipos restantes de primos. Por ejemplo, el pseudoprimo de tipo Q más pequeño 50,972,694,899,204,437,633 calculado por Holger Stephan (2019) se expone mediante las condiciones de firma 14a y 14c en Adams & Shanks (1982 , p. 257) .
↑ Kurtz, Shanks y Williams (1986 , pág. 697)
↑ Stephan (2019)
↑ Adams y Shanks (1982 , págs. 280-283)
↑ La implementación en AC/C++ de la prueba Perrin extendida se puede encontrar en la subsección final de una versión anterior de este artículo.
↑ Stephan (2019)

Referencias

Lucas, E. (1878). "Teoría de las funciones numéricas simples y periódicas" . Revista Estadounidense de Matemáticas (en francés). 1 (3). Prensa de la Universidad Johns Hopkins: 229– 231. doi : 10.2307/2369311 . JSTOR 2369311 .
Tarry, G. (1898). "Pregunta 1401". L'Intermédiaire des Mathématiciens . 5 . Gauthier-Villars et fils: 266-267 .
Perrin, R. [en francés] (1899). «Pregunta 1484» . L'Intermédiaire des Mathématiciens . 6 . Gauthier-Villars et fils: 76-77 .
Malo, E. (1900). "Respuesta a 1484". L'Intermédiaire des Mathématiciens . 7 . Gauthier-Villars et fils: 280-282 , 312-314 .
Jarden, Dov (1966). Secuencias recurrentes (PDF) (2 ed.). Jerusalén: Riveon LeMatematika. págs. 86 a 93.
Adams, William; Shanks, Daniel (1982). "Pruebas de primalidad fuertes que no son suficientes" . Mathematics of Computation . 39 (159). American Mathematical Society : 255–300 . doi : 10.1090/S0025-5718-1982-0658231-9 . JSTOR 2007637 .
Kurtz, GC; Shanks, Daniel ; Williams, HC (1986). "Pruebas rápidas de primalidad para números menores que 50∙10 ⁹ " . Mathematics of Computation . 46 ( 174 ). American Mathematical Society : 691–701 . doi : 10.1090/S0025-5718-1986-0829639-7 . JSTOR 2008007 .
Füredi, Zoltán (1987). "El número de conjuntos independientes máximos en grafos conectados". Journal of Graph Theory . 11 (4): 463– 470. doi : 10.1002/jgt.3190110403 .
Arno, Steven (1991). "Una nota sobre los pseudoprimos de Perrin" . Matemáticas de la Computación . 56 (193). Sociedad Matemática Americana : 371–376 . Bibcode : 1991MaCom..56..371A . doi : 10.1090/S0025-5718-1991-1052083-9 . JSTOR 2008548 .
Grantham, Jon (2010). "Hay infinitos pseudoprimos de Perrin". Journal of Number Theory . 130 (5): 1117– 1128. arXiv : 1903.06825 . doi : 10.1016/j.jnt.2009.11.008 .
Jacobsen, Dana (2020). "Estadísticas y tablas pseudoprimas" . ntheory.org . Consultado el 7 de marzo de 2024. #LPSP Lucas-Selfridge
Stephan, Holger (2020). "Millones de pseudoprimos de Perrin, incluyendo algunos gigantes". arXiv : 2002.03756v1 [ math.NA ].
Stephan, Holger (2019). Pseudoprimos de Perrin (Datos de investigación WIAS n.º 4). Berlín: Instituto Weierstrass . doi : 10.20347/WIAS.DATA.4 .

Enlaces externos

Jacobsen, Dana (2016). "Pruebas de primalidad de Perrin".
Wright, Colin (2015). "Encontrando pseudoprimos de Perrin".
"Secuencia de Perrin" . MathPages.com .
"Pseudoprimos de Lucas y Perrin" . MathPages.com .
Holzbaur, Christian (1997). "Perrin Pseudoprimos".
Turk, Richard (2014). "La pizarra de Perrin".

[A001608-1] 1 2Sloane, N. J. A. (ed.). "SequenceA001608(Perrin sequence (or Ondrej Such sequence): a(n) = a(n-2) + a(n-3) with a(0) = 3, a(1) = 0, a(2) = 2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[2] Sloane, N. J. A. (ed.). "SequenceA078712(Series expansion of (-3 - 2*x)/(1 + x - x^3) in powers of x)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[3] Sloane, N. J. A. (ed.). "SequenceA112881(Indices of prime Perrin numbers; values of n such that A001608(n) is prime)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[4] Sloane, N. J. A. (ed.). "SequenceA074788(Prime numbers in the Perrin sequence b(n+1) = b(n-1) + b(n-2) with initial values b(1)=3, b(2)=0, b(3)=2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[5] Lucas (1878)

[6] Perrin (1899)

[7] Adams & Shanks (1982)

[8] Kurtz, Shanks & Williams (1986)

[9] Füredi (1987)

[10] Tarry (1898)

[11] Sloane, N. J. A. (ed.). "SequenceA000918(a(n) = 2^n − 2)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[12] Perrin (1899) translated from the French

[13] Malo (1900), Jarden (1966)

[14] Adams & Shanks (1982, p. 255)

[15] Grantham (2010), Stephan (2020)

[16] Sloane, N. J. A. (ed.). "Secuencia A013998 (pseudoprimos de Perrin sin restricciones)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.

[17] Sloane, N. J. A. (ed.). "Secuencia A018187 (pseudoprimos de Perrin restringidos)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.

[18] Sloane, N. J. A. (ed.). "Secuencia A275612 (pseudoprimos de Perrin restringidos (definición de Adams y Shanks))" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.

[19] Sloane, N. J. A. (ed.). "Secuencia A275613 (Pseudoprimos de Perrin restringidos (definición de Grantham))" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.

[20] Ninguno de los 2402549 pseudoprimos de Lucas-Selfridge por debajo de $1015$ enumerados por Dana Jacobsen (2020) es también un pseudoprimo de Perrin.

[21] Adams y Shanks (1982 , págs. 265, 269-270)

[22] Adams y Shanks (1982 , pág. 275) , Kurtz, Shanks y Williams (1986 , pág. 694) . Esto fue confirmado posteriormente para $n < 10$ $14$ por Steven Arno (1991) .

[23] La firma sí proporciona información discriminatoria sobre los dos tipos restantes de primos. Por ejemplo, el pseudoprimo de tipo Q más pequeño 50,972,694,899,204,437,633 calculado por Holger Stephan (2019) se expone mediante las condiciones de firma 14a y 14c en Adams & Shanks (1982 , p. 257) .

[24] Kurtz, Shanks y Williams (1986 , pág. 697)

[25] Stephan (2019)

[26] Adams y Shanks (1982 , págs. 280-283)

[27] La implementación en AC/C++ de la prueba Perrin extendida se puede encontrar en la subsección final de una versión anterior de este artículo.

[28] Stephan (2019)

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 1 ]

[

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[26]

[27]

[28]