La secuencia de Sylvester

Sucesión de números enteros doblemente exponencial

Demostración gráfica de la convergencia de la suma 1/2 + 1/3 + 1/7 + 1/43 + ... a 1. Cada fila de k cuadrados con lados de longitud 1/ k tiene un área total de 1/ k , y todos los cuadrados juntos cubren exactamente un cuadrado más grande con un área de 1. Los cuadrados con lados de longitud 1/1807 o menores son demasiado pequeños para verse en la figura y no se muestran.

En teoría de números , la sucesión de Sylvester es una sucesión de números enteros en la que cada término es el producto de los términos anteriores más uno. Sus primeros términos son

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (secuencia A000058 en la OEIS ).

La secuencia de Sylvester recibe su nombre en honor a James Joseph Sylvester , quien la investigó por primera vez en 1880. ^[1] Sus valores crecen de forma exponencial doble , y la suma de sus recíprocos forma una serie de fracciones unitarias que converge a 1 más rápidamente que cualquier otra serie de fracciones unitarias. ^[2] La recurrencia por la que se define permite que los números de la secuencia se factoricen más fácilmente que otros números de la misma magnitud, ^[3] pero, debido al rápido crecimiento de la secuencia, solo se conocen factorizaciones primas completas para algunos de sus términos. ^[4] Los valores derivados de esta secuencia también se han utilizado para construir representaciones de fracciones egipcias finitas de 1, variedades de Einstein de Sasakian , ^[5] e instancias duras para algoritmos en línea . ^[6]

Definiciones formales

Formalmente, la secuencia de Sylvester se puede definir mediante la fórmula ^[7]

${\displaystyle s_{n}=1+\prod _{i=0}^{n-1}s_{i}.}$

El producto del conjunto vacío es 1, ^[8] por lo que esta fórmula da s _{0 = 2, sin necesidad de un} caso base separado .

Alternativamente, se puede definir la secuencia por la recurrencia ^[3]

${\displaystyle \displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1,}$con el caso base s ₀ = 2.

Es fácil demostrar por inducción que esto es equivalente a la otra definición. ^[9]

Fórmula de forma cerrada y asintótica

Los números de Sylvester crecen exponencialmente al doble en función de n . En concreto, se puede demostrar que

${\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor ,\!}$

para un número E que es aproximadamente 1,26408473530530... ^[10] (secuencia A076393 en la OEIS ). Esta fórmula tiene el efecto del siguiente algoritmo :

s ₀ es el entero más cercano a E ² ; s ₁ es el entero más cercano a E ⁴ ; s ₂ es el entero más cercano a E ⁸ ; para s _n , tome E ² , elévelo al cuadrado n veces más y tome el entero más cercano.

Este sólo sería un algoritmo práctico si tuviéramos una mejor manera de calcular E con el número requerido de lugares que calcular s _n y tomar su raíz cuadrada repetida . ^[11]

El crecimiento doblemente exponencial de la secuencia de Sylvester no es sorprendente si se lo compara con la secuencia de números de Fermat F _n ; los números de Fermat se definen habitualmente mediante una fórmula doblemente exponencial, , pero también pueden definirse mediante una fórmula de producto muy similar a la que define la secuencia de Sylvester: ^[12] ${\displaystyle 2^{2^{n}}\!+1}$

${\displaystyle F_{n}=2+\prod _{i=0}^{n-1}F_{i}.}$

Conexión con fracciones egipcias

Las fracciones unitarias formadas por los recíprocos de los valores de la secuencia de Sylvester generan una serie infinita : ^[13]

${\displaystyle \sum _{i=0}^{\infty }{\frac {1}{s_{i}}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .}$

Las sumas parciales de esta serie tienen una forma simple,

${\displaystyle \sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=1-{\frac {1}{s_{j}-1}}={\frac {s_{j}-2}{s_{j}-1}},}$

que ya está en términos mínimos. ^[14] Esto puede demostrarse por inducción, o más directamente notando que la recursión implica que

${\displaystyle {\frac {1}{s_{i}-1}}-{\frac {1}{s_{i+1}-1}}={\frac {1}{s_{i}}},}$

Así que la suma de los telescopios ^[14]

${\displaystyle \sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=\sum _{i=0}^{j-1}\left({\frac {1}{s_{i}-1}}-{\frac {1}{s_{i+1}-1}}\right)={\frac {1}{s_{0}-1}}-{\frac {1}{s_{j}-1}}=1-{\frac {1}{s_{j}-1}}.}$

Dado que esta secuencia de sumas parciales ( s _j − 2)/( s _j − 1) converge a uno, la serie general forma una representación fraccionaria egipcia infinita del número uno:

${\displaystyle 1={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .}$

Se pueden encontrar representaciones de fracciones egipcias finitas de uno, de cualquier longitud, truncando esta serie y restando uno del último denominador:

${\displaystyle 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{6}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{42}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{43}}+{\tfrac {1}{1806}},\quad \dots .}$

La suma de los primeros k términos de la serie infinita proporciona la subestimación más cercana posible de 1 para cualquier fracción egipcia de k términos. ^[2] Por ejemplo, los primeros cuatro términos suman 1805/1806 y, por lo tanto, cualquier fracción egipcia para un número en el intervalo abierto (1805/1806, 1) requiere al menos cinco términos.

Es posible interpretar la sucesión de Sylvester como el resultado de un algoritmo voraz para fracciones egipcias , que en cada paso elige el menor denominador posible que haga que la suma parcial de la serie sea menor que uno. ^[15]

Singularidad de series de rápido crecimiento con sumas racionales

Como observó el propio Sylvester, la secuencia de Sylvester parece ser única por tener valores que crecen tan rápidamente y, al mismo tiempo, tener una serie de recíprocos que convergen a un número racional . Esta secuencia proporciona un ejemplo que muestra que el crecimiento doblemente exponencial no es suficiente para hacer que una secuencia de números enteros sea una secuencia de irracionalidad . ^[16]

Para hacer esto más preciso, se deduce de los resultados de Badea (1993) que, si una secuencia de números enteros crece lo suficientemente rápido como para que ${\displaystyle a_{n}}$

${\displaystyle a_{n}\geq a_{n-1}^{2}-a_{n-1}+1,}$

Y si la serie

${\displaystyle A=\sum {\frac {1}{a_{i}}}}$

converge a un número racional A , entonces, para todo n después de algún punto, esta secuencia debe estar definida por la misma recurrencia

${\displaystyle a_{n}=a_{n-1}^{2}-a_{n-1}+1}$

que puede utilizarse para definir la secuencia de Sylvester. ^[17]

Erdős y Graham (1980) conjeturaron que, en resultados de este tipo, la desigualdad que limita el crecimiento de la secuencia podría ser reemplazada por una condición más débil, ^[18]

${\displaystyle \lim _{n\rightarrow \infty }{\frac {a_{n}}{a_{n-1}^{2}}}=1.}$

Badea (1995) analiza los avances relacionados con esta conjetura ; véase también Brown (1979). ^[19]

Divisibilidad y factorizaciones

Si i < j , se deduce de la definición que s _j ≡ 1 (mod s _i  ). Por lo tanto, cada dos números en la secuencia de Sylvester son primos entre sí . La secuencia se puede utilizar para demostrar que hay infinitos números primos , ya que cualquier primo puede dividir como máximo un número en la secuencia. Más fuertemente, ningún factor primo de un número en la secuencia puede ser congruente con 5 módulo 6, y la secuencia se puede utilizar para demostrar que hay infinitos primos congruentes con 7 módulo 12. ^[20]

Problema sin resolver en matemáticas :

¿Todos los términos de la secuencia de Sylvester son libres de cuadrados?

(más problemas sin resolver en matemáticas)

Aún queda mucho por saber sobre la factorización de los números de la sucesión de Sylvester. Por ejemplo, no se sabe si todos los números de la sucesión son libres de cuadrados , aunque todos los términos conocidos lo son. ^[21]

Como describe Vardi (1991), es fácil determinar cuál número de Sylvester (si lo hay) divide un primo p dado: simplemente calcule la recurrencia que define los números módulo p hasta encontrar un número que sea congruente con cero (mod p ) o encuentre un módulo repetido. ^[3] Usando esta técnica, encontró que 1166 de los primeros tres millones de primos son divisores de números de Sylvester, ^[22] y que ninguno de estos primos tiene un cuadrado que divida un número de Sylvester. El conjunto de primos que pueden aparecer como factores de números de Sylvester es de densidad cero en el conjunto de todos los primos: ^[23] de hecho, el número de tales primos menores que x es . ^[24] ${\displaystyle O(\pi (x)/\log \log \log x)}$

La siguiente tabla muestra factorizaciones conocidas de estos números (excepto los primeros cuatro, que son todos primos): ^[4]

Como es habitual, P n y C n denotan números primos y números compuestos no factorizados de n dígitos de longitud.

Aplicaciones

Boyer, Galicki y Kollár (2005) utilizan las propiedades de la secuencia de Sylvester para definir grandes cantidades de variedades de Einstein de Sasaki que tienen la topología diferencial de esferas de dimensión impar o esferas exóticas . Demuestran que la cantidad de métricas de Einstein de Sasaki distintas en una esfera topológica de dimensión 2 n  − 1 es al menos proporcional a s _n y, por lo tanto, tiene un crecimiento exponencial doble con n . ^[5]

Como describen Galambos y Woeginger (1995), Brown (1979) y Liang (1980) utilizaron valores derivados de la secuencia de Sylvester para construir ejemplos de límites inferiores para algoritmos de empaquetamiento de contenedores en línea . ^[6] Seiden y Woeginger (2005) utilizan de manera similar la secuencia para limitar inferiormente el rendimiento de un algoritmo de stock de corte bidimensional. ^[25]

El problema de Znám se refiere a conjuntos de números tales que cada número en el conjunto divide pero no es igual al producto de todos los demás números, más uno. Sin el requisito de desigualdad, los valores en la secuencia de Sylvester resolverían el problema; con ese requisito, tiene otras soluciones derivadas de recurrencias similares a la que define la secuencia de Sylvester. Las soluciones al problema de Znám tienen aplicaciones en la clasificación de singularidades superficiales (Brenton y Hill 1988) y en la teoría de autómatas finitos no deterministas . ^[26]

Curtiss (1922) describe una aplicación de las aproximaciones más cercanas a uno por sumas de k términos de fracciones unitarias, para limitar inferiormente el número de divisores de cualquier número perfecto , y Miller (1919) usa la misma propiedad para limitar superiormente el tamaño de ciertos grupos . ^[27]

Véase también

• La constante de Cahen
• Número pseudoperfecto primario
• Número de Leonardo

Notas

1. Silvestre (1880).
2. Esta afirmación se atribuye comúnmente a Curtiss (1922), pero Miller (1919) parece haber hecho la misma afirmación en un artículo anterior. Véase también Rosenman y Underwood (1933), Salzer (1947), Soundararajan (2005) y Nathanson (2023).
3. Vardi (1991).
4. Todos los factores primos p de los números de Sylvester s _n con p < 5 × 10Vardi enumera ⁷ y n ≤ 200. Ken Takusagawa enumera las factorizaciones hasta s9 y la factorización de s10. Las factorizaciones restantes proceden de una lista de factorizaciones de la sucesión de Sylvester mantenida por Jens Kruse Andersen. Consultado el 13 de junio de 2014.
5. Boyer, Galicki y Kollár (2005).
6. Galambos y Woeginger (1995); Brown (1979); Liang (1980).
7. Sloane, N. J. A. (ed.). "Secuencia A000058 (secuencia de Sylvester)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
8. Nešetřil y Matoušek (1998).
9. Sylvester (1880), pág. 333, ofrece una prueba por inducción.
10. Graham, Knuth y Patashnik (1989), fórmula 4.17, pág. 109, y ejercicio 4.37, pág. 147; véase también Golomb (1963).
11. Graham, Knuth y Patashnik (1989), pág. 109.
12. Sloane, N. J. A. (ed.). "Secuencia A000215 (números de Fermat)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
13. Esta serie es el punto de partida de Sylvester (1880)
14. Sylvester (1880), pág. 334.
15. Nathanson (2023).
16. Chico (2004).
17. Badea (1993).
18. Erdős y Graham (1980).
19. Badea (1995); Marrón (1979).
20. Guy y Nowakowski (1975).
21. Graham, Knuth y Patashnik (1989), problema de investigación 4.65, pág. 151; Vardi (1991); véase también Chentouf (2020)
22. Esto parece ser un error tipográfico, ya que Andersen encuentra 1167 divisores primos en este rango.
23. Jones (2006).
24. Odoni (1985).
25. En su trabajo, Seiden y Woeginger se refieren a la secuencia de Sylvester como "secuencia de Salzer" en honor al trabajo de Salzer (1947) sobre la aproximación más cercana.
26. Domaratzki y otros (2005).
27. Curtiss (1922); Miller (1919).

Referencias

• Badea, Catalin (1993). "Un teorema sobre la irracionalidad de las series infinitas y aplicaciones". Acta Arithmetica . 63 (4): 313–323. doi : 10.4064/aa-63-4-313-323 . MR  1218459.
• Badea, Catalin (1995). "Sobre algunos criterios de irracionalidad para series de racionales positivos: un estudio" (PDF) . Archivado desde el original (PDF) el 11 de septiembre de 2008.
• Boyer, Charles P.; Galicki, Krzysztof; Kollár, János (2005). "Métricas de Einstein sobre esferas". Anales de Matemáticas . 162 (1): 557–580. arXiv : math.DG/0309408 . doi : 10.4007/annals.2005.162.557. SEÑOR  2178969. S2CID  13945306.
• Brenton, Lawrence; Hill, Richard (1988). "Sobre la ecuación diofántica 1=Σ1/ni + 1/Πni y una clase de singularidades superficiales complejas homológicamente triviales". Revista del Pacífico de Matemáticas . 133 (1): 41–67. doi : 10.2140/pjm.1988.133.41 . MR  0936356.
• Brown, DJ (1979). Un límite inferior para algoritmos de empaquetamiento de contenedores unidimensionales en línea . Tech. Rep. R-864. Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign.
• Chentouf, A. Anas (2020). "Sobre la sucesión de Sylvester y algunas de sus propiedades" (PDF) . Parábola . 56 (2).
• Curtiss, DR (1922). "Sobre el problema diofántico de Kellogg". American Mathematical Monthly . 29 (10): 380–387. doi :10.2307/2299023. JSTOR  2299023.
• Domaratzki, Michael; Ellul, Keith; Shallit, Jeffrey ; Wang, Ming-Wei (2005). "No unicidad y radio de los NFA unarios cíclicos". Revista internacional de fundamentos de la ciencia informática . 16 (5): 883–896. doi :10.1142/S0129054105003352. MR  2174328.
• Erdős, Paul ; Graham, Ronald L. (1980). Viejos y nuevos problemas y resultados de la teoría combinatoria de números . Monografías de L'Enseignement Mathématique, núm. 28, Univ. de Ginebra. SEÑOR  0592420.
• Galambos, Gábor; Woeginger, Gerhard J. (1995). "Embalaje de contenedores en línea: un estudio restringido". Métodos matemáticos de investigación de operaciones . 42 (1): 25. doi :10.1007/BF01415672. MR  1346486. S2CID  26692460.
• Golomb, Solomon W. (1963). "Sobre ciertas secuencias recurrentes no lineales". American Mathematical Monthly . 70 (4): 403–405. doi :10.2307/2311857. JSTOR  2311857. MR  0148605.
• Graham, Ronald ; Knuth, Donald E .; Patashnik, Oren (1989). Matemáticas concretas (2.ª ed.). Addison-Wesley . ISBN 978-0-201-55802-9.
• Guy, Richard K. (2004). "E24 Irracionalidad en secuencias". Problemas sin resolver en teoría de números (3.ª ed.). Springer-Verlag . pág. 346. ISBN 0-387-20860-7.Zbl 1058.11001  .
• Guy, Richard; Nowakowski, Richard (1975). "Descubrimiento de números primos con Euclides". Delta (Waukesha) . 5 (2): 49–63. MR  0384675.
• Jones, Rafe (2006). "La densidad de divisores primos en la dinámica aritmética de polinomios cuadráticos". Revista de la Sociedad Matemática de Londres . 78 (2): 523–544. arXiv : math.NT/0612415 . Bibcode :2006math.....12415J. doi :10.1112/jlms/jdn034. S2CID  15310955.
• Liang, Frank M. (1980). "Un límite inferior para el empaquetamiento de contenedores en línea". Information Processing Letters . 10 (2): 76–79. doi :10.1016/S0020-0190(80)90077-0. MR  0564503.
• Nešetřil, Jaroslav ; Matoušek, Jiří (1998). Invitación a Matemática Discreta . Prensa de la Universidad de Oxford. pag. 12.ISBN​ 0-19-850207-9.
• Miller, GA (1919). "Grupos que poseen un pequeño número de conjuntos de operadores conjugados". Transactions of the American Mathematical Society . 20 (3): 260–270. doi : 10.2307/1988867 . JSTOR  1988867.
• Nathanson, Melvyn B. (enero de 2023). "Subaproximación mediante fracciones egipcias". Journal of Number Theory . 242 : 208–234. arXiv : 2202.00191 . doi :10.1016/j.jnt.2022.07.005.
• Odoni, RWK (1985). "Sobre los divisores primos de la sucesión w _n+1 =1+w ₁ ⋯w _n ". Revista de la Sociedad Matemática de Londres . Serie II. 32 : 1–11. doi :10.1112/jlms/s2-32.1.1. Zbl  0574.10020.
• Rosenman, Martin; Underwood, F. (1933). "Problema 3536". American Mathematical Monthly . 40 (3): 180–181. doi :10.2307/2301036. JSTOR  2301036.
• Salzer, HE (1947). "La aproximación de números como sumas de recíprocos". American Mathematical Monthly . 54 (3): 135–142. doi :10.2307/2305906. JSTOR  2305906. MR  0020339.
• Seiden, Steven S.; Woeginger, Gerhard J. (2005). "El problema del material de corte bidimensional revisitado". Programación matemática . 102 (3): 519–530. doi :10.1007/s10107-004-0548-1. MR  2136225. S2CID  35815524.
• Soundararajan, K. (2005). "Aproximación de 1 desde abajo usando n fracciones egipcias". arXiv : math.CA/0502247 .
• Sylvester, JJ (1880). "Sobre un punto en la teoría de fracciones vulgares". American Journal of Mathematics . 3 (4): 332–335. doi :10.2307/2369261. JSTOR  2369261.
• Vardi, Ilan (1991). Recreaciones computacionales en Mathematica . Addison-Wesley. Págs. 82-89. ISBN. 0-201-52989-0.

Enlaces externos

• Irracionalidad de las sumas cuadráticas, de MathPages de KS Brown.
• Weisstein, Eric W. "La secuencia de Sylvester". MundoMatemático .