Número de Perrin

Secuencia numérica 3,0,2,3,2,5,5,7,10,...

Espiral de triángulos equiláteros con longitudes de lados iguales a los números de Perrin.

En matemáticas, los números de Perrin son una secuencia de números enteros recursivos constantes doblemente infinitas con ecuación característica x ³ = x + 1 . Los números de 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 por la relación de recurrencia

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

y el reverso

${\displaystyle P(n)=P(n+3)-P(n+1){\mbox{ for }}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

${\displaystyle {\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 sucesión y su ecuación , y observó que el índice n divide al término P(n) si n es primo. ^[5] En 1899, Raoul Perrin preguntó si existían contraejemplos de esta propiedad. ^[6] El primer P(n) divisible por el índice compuesto n fue descubierto recién en 1982 por William Adams y Daniel Shanks . ^[7] Presentaron una investigación detallada de la sucesión, y una secuela apareció cuatro años después. ^[8]

Propiedades

Un microcosmos de Perrin: el algoritmo de tiempo de escape se aplica al mapa de Newton de toda la función de Perrin F(z) alrededor del punto crítico z = 1,225432 con un ancho de ventana gráfica de 0,05320. Las cuencas de atracción que emanan del centro corresponden al número infinito de raíces reales (izquierda) y complejas (derecha) F(z) = 0 .

La secuencia de Perrin también satisface la relación de recurrencia. A partir de ésta y de la recurrencia definitoria, se pueden crear un número infinito de relaciones adicionales, por ejemplo ${\displaystyle P(n)=P(n-1)+P(n-5).}$ ${\displaystyle P(n)=P(n-3)+P(n-4)+P(n-5).}$

La función generadora de la secuencia de Perrin es

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

La secuencia está relacionada con las sumas de coeficientes binomiales por

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

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

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

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

Los números de Perrin se obtienen como potencias integrales n ≥ 0 de la matriz

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

y su inversa

${\displaystyle {\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 está dado por el determinante

${\displaystyle {\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 diferentes conjuntos independientes máximos en un gráfico de ciclo de n vértices se cuenta mediante el n -ésimo número de Perrin para n ≥ 2. [ ^9]

Fórmula de Binet

La función Perrin extiende la secuencia a números reales.

La solución de la recurrencia se puede escribir en términos de las raíces de la ecuación característica . Si las tres soluciones son raíz real ⁠ ⁠ (con valor aproximado 1,324718 y conocida como razón plástica ) y raíces conjugadas complejas ⁠ ⁠ y ⁠ ⁠ , los números de Perrin se pueden calcular con la fórmula de Binet que también es válida para n negativo . ${\displaystyle P(n)=P(n-2)+P(n-3)}$ ${\displaystyle x^{3}-x-1=0}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle P(n)=\alpha ^{n}+\beta ^{n}+\gamma ^{n},}$

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

Al expandir la identidad se obtiene la importante regla de duplicación del índice mediante la cual se vinculan las partes directa e inversa de la secuencia. ${\displaystyle P^{2}(n)=(\alpha ^{n}+\beta ^{n}+\gamma ^{n})^{2}}$ ${\displaystyle P(2n)=P^{2}(n)-2P(-n),}$

Índice principalpagdividePáginas)

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

${\displaystyle {\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 con valores enteros son los polinomios simétricos elementales en ${\displaystyle \alpha ,\beta ,\gamma .}$

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

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

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

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

${\displaystyle (a+b+c)^{n}-(a^{n}+b^{n}+c^{n})=}$ ${\displaystyle \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}.}$

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

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

Prueba de primalidad de Perrin

Consulta 1484. La curiosa proposición de origen chino que es objeto de la consulta 1401 ^[10] proporcionaría, de ser 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 calcular los residuos respecto de m de términos sucesivos de la sucesión de recurrencia
u _n = 3u _n−1 − 2u _n−2 con valores iniciales u ₀ = −1, u ₁ = 0. ^[11]
He encontrado otra sucesión 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 ₀ = 3, v ₁ = 0, v ₂ = 2. Es fácil demostrar que v _n es divisible por n, si n es primo; He comprobado, hasta valores bastante elevados de n, que en el caso contrario no es así; pero sería interesante saber si esto es realmente así, sobre todo porque la sucesión v _n da números que crecen mucho menos rápidamente que la sucesión u _n (para n = 17, por ejemplo, se encuentra u _n = 131070, v _n = 119), lo que conduce a cálculos más sencillos cuando n es un número grande.
La misma demostración, aplicable a una de las sucesiones, se aplicará sin duda a la otra, si la propiedad enunciada es verdadera para ambas: sólo es cuestión de descubrirla. ^[12]

La sucesión de Perrin tiene la propiedad de Fermat : si p es primo , P(p) ≡ P(1) ≡ 0 (mod p) . Sin embargo, la inversa no es cierta: algún número compuesto n puede dividir a 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 ninguno era conocido hasta que Adams y Shanks encontraron el más pequeño, 271441 = 521 ² (el número P(271441) tiene 33150 dígitos decimales). ^[14] Jon Grantham demostró más tarde que hay infinitos pseudoprimos de Perrin. ^[15]

Los diecisiete pseudoprimos de Perrin por debajo de 10 ⁹ son

271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 45670533, 801123451, 855073301, 903136901, 970355431. ^[16]

Adams y Shanks observaron que los números primos también satisfacen la congruencia P(−p) ≡ P(−1) ≡ −1 (mod p) . Los números compuestos para los cuales se cumplen ambas propiedades se denominan pseudoprimos de Perrin restringidos. Solo hay nueve números de este tipo por debajo de 10 ⁹ . ^{[17] [18] [19]}

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

Pseudocódigo

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

Se inicializan dos matrices de enteros u(3) y v(3) en 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 doble y suma , originalmente diseñado para ejecutarse en una calculadora de bolsillo HP-41C , calcula P(n) mod n y el inverso P(−n) mod n al costo de seis cuadraturas modulares para cada bit de n .

Los subíndices de los números de Perrin se duplican utilizando la identidad P(2t) = P ² (t) − 2P(−t) . Las brechas resultantes entre P(±2t) y P(±2t ± 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):= 1 Prueba número positivo impar n entrada  int n conjunto  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 temperatura:= u(i)^2 − 2v(i) (mód n) v(i):= v(i)^2 − 2u(i) (mód n) u(i):= temperatura fin para  Copie P(2t + 2) y P(−2t − 2)  en los extremos de la matriz y utilícelos  en la declaración if a continuación. u(3):= u(2) v(3):= v(2)  Sobrescribir P(2t ± 2) con P(2t ± 1) temperatura:= u(2) − u(1) u(2):= u(0) + temperatura u(0):= temperatura  Sobrescribir P(−2t ± 2) con P(−2t ± 1) temperatura:= v(0) − v(1) v(0):= v(2) + temperatura v(2):= temperatura  Si n tiene el bit k establecido , entonces  aumente los índices de  ambos triples de Perrin en 1.  para i = 0, 1, 2 u(i):= u(i + 1) v(i):= v(i + 1) fin para fin  si fin para Resultado 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: primo real 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 ≈ 1 / 6 de todos los primos, por lo que los dos conjuntos no se pueden distinguir solo con la fuerza de 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):= 1v(0):= 3, v(1):= 0, v(2):=−2

Se aplica la misma regla de duplicación y las fórmulas para llenar los espacios son

temperatura:= u(0) + u(1)u(0):= u(2) − temperaturau(2):= temperatura temperatura:= v(2) + v(1)v(2):= v(0) − temperaturav(0):= temperatura

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 ⁹ 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 elevará a 4.057.052.731.496.380.171 = 1424263447 ∙ 2848526893. ^[25]

Además, las raíces de la regla de duplicación-congruencia distintas de −1 o 3 exponen números compuestos, como raíces cuadradas no triviales de 1 en la prueba de Miller-Rabin . ^[26] Esto reduce el número de pseudoprimos restringidos para cada secuencia en aproximadamente un tercio y es especialmente eficiente para detectar números de Carmichael . ^[27] ${\displaystyle x^{2}-2x\equiv 3=P(0){\pmod {n}}\,}$

El pseudoprimo de Perrin restringido menos fuerte es 46672291 y los dos límites anteriores se expanden sucesivamente a 173.536.465.910.671 y 79.720.990.309.209.574.421. ^[28]

Notas

1. Sloane, N. J. A. (ed.). "Secuencia A001608 (secuencia de Perrin (o secuencia de Ondrej Such): a(n) = a(n-2) + a(n-3) con a(0) = 3, a(1) = 0, a(2) = 2)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
2. Sloane, N. J. A. (ed.). "Secuencia A078712 (Expansión en serie de (-3 - 2*x)/(1 + x - x^3) en potencias de x)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
3. Sloane, N. J. A. (ed.). "Secuencia A112881 (Índices de números primos de Perrin; valores de n tales que A001608(n) es primo)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
4. Sloane, N. J. A. (ed.). "Secuencia A074788 (Números primos en la secuencia de Perrin b(n+1) = b(n-1) + b(n-2) con valores iniciales b(1)=3, b(2)=0, b(3)=2)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
5. Lucas (1878)
6. Perrin (1899)
7. Adams y Shanks (1982)
8. Kurtz, Shanks y Williams (1986)
9. Furedi (1987)
10. Alto (1898)
11. Sloane, N. J. A. (ed.). "Secuencia A000918 (a(n) = 2^n - 2)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
12. Perrin (1899) traducido del francés
13. Malo (1900), Jarden (1966)
14. Adams y Shanks (1982, pág. 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 números enteros . Fundación OEIS.
17. Sloane, N. J. A. (ed.). "Secuencia A018187 (Pseudoprimos de Perrin restringidos)". La enciclopedia en línea de secuencias de números 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 números 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 números enteros . Fundación OEIS.
20. Ninguno de los 2402549 pseudoprimos de Lucas-Selfridge por debajo de 10 ¹⁵ enumerados por Dana Jacobsen (2020) es también un pseudoprimo de Perrin.
21. Adams y Shanks (1982, pág. 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 ¹⁴ por Steven Arno (1991).
23. La firma sí brinda información discriminante 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), queda expuesto por las condiciones de firma 14a y 14c en Adams & Shanks (1982, p. 257).
24. Kurtz, Shanks y Williams (1986, pág. 697)
25. Esteban (2019)
26. Adams y Shanks (1982, págs. 280-283)
27. La implementación 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. Esteban (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–93.
• Adams, William; Shanks, Daniel (1982). "Pruebas de primalidad fuertes que no son suficientes". Matemáticas de la computación . 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∙109". Matemáticas de la computación . 46 (174). Sociedad Matemática Americana : 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 conexos". 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). American Mathematical Society : 371–376. Bibcode :1991MaCom..56..371A. doi : 10.1090/S0025-5718-1991-1052083-9 . JSTOR  2008548.
• Grantham, Jon (2010). "Existen 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 de pseudoprime". ntheory.org . Consultado el 7 de marzo de 2024. #LPSP Lucas-Selfridge
• Stephan, Holger (2020). "Millones de pseudoprimos de Perrin, incluidos algunos gigantes". arXiv : 2002.03756v1 [math.NA].
• Stephan, Holger (2019). Pseudoprimes de Perrin (datos de investigación WIAS n.º 4). Berlín: Weierstrass Institute . doi : 10.20347/WIAS.DATA.4 .

Enlaces externos

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