Secuencia de Silvestre

La secuencia de Sylvester es una secuencia entera en la que cada miembro sucesivo es igual al producto de los miembros anteriores más uno. Los primeros miembros de la secuencia son:

2 , 3 , 7 , 43 , 1807, 3263443, 10650056950807, 113423713055421850000000000, … (secuencia A000058 en OEIS ).

Nombrado así por James Sylvester , quien lo exploró por primera vez en 1880 . Los valores de sus términos crecen como el doble exponente , y la suma de los términos recíprocos forma una serie de fracciones de uno que converge a 1 más rápido que cualquier otra serie de fracciones de uno con el mismo número de términos. La relación de recurrencia , que define los términos de la sucesión, permite que los números de la sucesión se factoricen más fácilmente que otros números del mismo orden, pero debido al crecimiento muy rápido de los términos de la serie, una factorización completa en números primos factores se conoce sólo para algunos miembros de esta secuencia. Los valores obtenidos usando esta secuencia se usan para formar la representación final de 1 como una fracción egipcia , variedades Sasakian de Einstein, y como fuente de datos para algoritmos en línea .

Definiciones formales

Formalmente, la sucesión de Sylvester se puede definir mediante la fórmula:

{\displaystyle s_{n}=1+\prod_{i=0}^{n-1}s_{i))

El producto de los elementos del conjunto vacío es igual a 1, entonces. ${\ estilo de visualización s_ {0} = 2}$

Otra forma de definir una secuencia es con una relación de recurrencia :

{\ estilo de visualización \ estilo de visualización s_{i}=s_{i-1}(s_{i-1}-1)+1}

, donde .

{\ estilo de visualización s_ {0} = 2}

La equivalencia de las definiciones se prueba por inducción directa.

Fórmula general y asintóticas

Los términos de la sucesión de Sylvester crecen a razón del doble exponente . En particular, se puede demostrar que:

s_{n}=\left\lpiso E^{2^{n+1}}+{\frac {1}{2}}\right\rpiso,

donde el número es aproximadamente 1.264084735305302 [1] . Esta fórmula conduce al siguiente algoritmo : $mi$

s 0 es el entero más cercano a E 2 ; s 1 es el entero más próximo a E 4 ; s 2 es el entero más próximo a E 8 ; para s n , tome E 2 , elévelo al cuadrado n veces y tome el entero más cercano.

Este algoritmo sería aceptable si tuviéramos una mejor manera de calcular E en lugar de calcular s n y luego calcular raíces cuadradas .

El crecimiento de los elementos de la sucesión de Sylvester a una tasa exponencial doble no sorprende en absoluto si se compara con la sucesión de números de Fermat F n . Los números de Fermat suelen estar dados por la fórmula del doble exponente , pero también pueden estar dados por fórmulas de multiplicación similares a las de la sucesión de Sylvester: $2^{{2^{n}}}+1$

F_{n}=2+\prod_{i=0}^{n-1}F_{i}.

Conexión con las fracciones egipcias

Las fracciones de la unidad , formadas por números recíprocos a los valores de la secuencia de Sylvester, forman una serie infinita :

\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 la forma simple

\sum_{i=0}^{j-1}{\frac {1}{s_{i}}}=1-{\frac {1}{s_{j}-1}}={ \frac{s_{j}-2}{s_{j}-1}}.

Esto se puede demostrar por inducción o directamente al notar que la recursividad implica

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

Así, la suma de la fila telescópica será igual a

\sum_{i=0}^{j-1}{\frac {1}{s_{i))}=\sum_{i=0}^{j-1}\left({\ fracción {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 la secuencia de sumas parciales ( s j −2)/( s j −1) converge a 1, toda la serie forma una representación fraccionaria egipcia infinita de 1 :

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

Uno puede encontrar las representaciones finales de la unidad como una fracción egipcia de cualquier longitud terminando esta serie y restando uno del último denominador:

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 una serie infinita da el límite inferior más cercano para la unidad en fracciones egipcias de k términos. [2] Por ejemplo, los primeros cuatro términos se suman a 1805/1806, por lo que cualquier fracción egipcia en el intervalo abierto (1805/1806.1) requiere al menos cinco términos.

Se puede pensar en la sucesión de Sylvester como el resultado de un algoritmo codicioso de fracciones egipcias , que en cada paso elige el divisor más pequeño posible que deja la suma parcial menor que uno. Asimismo, los términos de la serie posteriores al primero pueden ser considerados como divisores de la aproximación codiciosa por números impares del número 1/2.

Singularidad de series de rápido crecimiento con sumas racionales

Como señaló el propio Sylvester, la secuencia de Sylvester parece ser la única que tiene tal tasa de crecimiento, mientras converge en un número racional. Esta secuencia muestra un ejemplo de que la tasa de crecimiento de un doble exponente no es suficiente para que una secuencia de números enteros sea una secuencia racional [3] .

Del resultado de Badea [4] se deduce que si una secuencia de números enteros crece lo suficientemente rápido como para que $un$

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

y si la fila

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

converge a un número racional A , entonces para todo n , comenzando desde algún lugar, esta secuencia debe satisfacer la relación de recurrencia

a_{n}=a_{n-1}^{2}-a_{n-1}+1

que se puede utilizar para determinar la sucesión de Sylvester.

Erdős [5] conjeturó que en resultados de este tipo, el límite de la desigualdad de crecimiento de secuencia puede ser reemplazado por una condición más débil

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

Divisibilidad y descomposición

Si i < j , se sigue de la definición que s j ≡ 1 (mod s i ). Por lo tanto, dos términos cualesquiera de la sucesión de Sylvester son coprimos . La sucesión se puede utilizar para demostrar la infinidad del número de primos , ya que cualquier número primo puede dividir como máximo a un número de la sucesión. Ningún factor primo de un número en la secuencia se puede comparar con 5 (módulo 6), y la secuencia se puede usar para probar que hay infinitos números primos comparables a 7 (módulo 12). [6]

Problemas no resueltos en matemáticas : ¿Todos los términos de la sucesión de Sylvester están libres de cuadrados ?

Queda mucho por saber acerca de la factorización de los términos de la sucesión de Sylvester. Por ejemplo, no se sabe si todos los miembros de la sucesión son libres de cuadrados , aunque todos los términos para los que se conoce la descomposición en factores primos sí lo son.

Como escribe Vardi ( 1991 ), es fácil determinar cuál de los términos de la sucesión de Sylvester (si los hay) es divisible por un número primo p ; simplemente calcule los residuos de los términos de la sucesión mod p de acuerdo con la fórmula recursiva hasta que se encuentra cero (mod p ) o el mismo resto. Usando esta técnica, Vardy encontró que 1166 del primer millón de números primos son divisores de los números de Sylvester, [7] y ningún cuadrado de estos números primos divide los números de Sylvester. El conjunto de primos que pueden ser divisores de los términos de la serie de Sylvester tiene densidad cero en el conjunto de todos los primos. Además, según Jones [8] , el número de primos menores que x es igual a . [9] $O(\pi (x)/\log \log \log x)$

La siguiente tabla enumera las expansiones conocidas de estos números (con la excepción de los primeros cuatro, que son primos): [10]

norte	Factores s n
cuatro	13×139
5	3263443, sencillo
6	547×607×1033×31051
7	29881 × 67003 × 9119521 × 6212157481
ocho	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × 3587438027224662415276456919113489495555972560447869169859142453622851
diez	2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
once	73 ×C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
catorce	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
quince	17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
dieciséis	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
Dieciocho	50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19	775608719589345260583891023073879169 × C106685
veinte	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

Aquí P n y C n denotan números primos y compuestos con n dígitos decimales.

Aplicaciones

Boyer, Galicki y Kollár ( Boyer, Galicki, Kollár 2005 ) utilizaron las propiedades de la secuencia de Sylvester para definir un gran número de variedades Sasakianas de Einstein que tienen la topología diferencial de esferas de dimensiones impares o esferas exóticas . Demostraron que el número de diferentes métricas de Sasakian Einstein en una esfera topológica de dimensión 2 n − 1 es al menos proporcional a s n y, por lo tanto, crece a una tasa exponencial doble (desde n ).

Como escriben Galambos y Woeginger ( 1995 ), Brown ( Brown 1979 ) y Liang ( Liang 1980 ) utilizaron valores derivados de la secuencia de Sylvester para construir ejemplos de un límite inferior para algoritmos de empaque de contenedores en línea . Seiden y Woeginger ( Seiden, Woeginger 2005 ) utilizaron de manera similar una secuencia para el límite inferior de rendimiento del algoritmo de anidamiento 2D [11] .

El problema de Znam es sobre conjuntos de números tales que cada número en el conjunto divide, pero no es igual al producto de todos los demás conjuntos más uno. Sin la condición de equivalencia, los valores de la secuencia de Sylvester resuelven este problema. Si se cumple esta condición, se obtiene otra solución a partir de una relación de recurrencia similar a la definición de la sucesión de Sylvester. Las soluciones al problema de Znam tienen aplicaciones para la clasificación de puntos singulares de superficies (Brenton, Hill 1988) y la teoría de autómatas finitos no deterministas . [12]

Curtis ( Curtiss 1922 ) describe la aplicación de la aproximación más cercana a la unidad por sumas de k -términos de fracciones de la unidad a un límite inferior en el número de divisores de cualquier número perfecto , y Müller ( Miller 1919 ) usa la misma propiedad para un menor limitado al número de algunos grupos .

Véase también

constante de caen
Número pseudoperfecto simple

Notas

↑ En Graham, Knuth y Patashnik ( 1989 ), esta declaración se da como ejercicio. Véase también Golomb ( Golomb 1963 ).
↑ Esta afirmación generalmente se atribuye a Curtis ( Curtiss 1922 ), pero Miller ( Miller 1919 ) hizo la misma afirmación en un trabajo anterior. Véase también Rosenman y Underwood 1933 , Salzer 1947 y ( Soundararajan 2005 ).
↑ Chico, 2004 .
↑ ( Badea 1993 )
↑ ( Erdős 1980 ), para una revisión de trabajos sobre esta hipótesis - ( Badea 1995 ), véase también Brown, 1979 .
↑ Chico, Nowakowski, 1975 .
↑ Parece que hay un error tipográfico aquí, ya que Andersen encontró 1167 divisores primos en este rango.
↑ Jones, 2006 .
↑ Odoni, 1985 .
↑ Vardy enumera todos los factores primos p de los números de Sylvester s n con p < 5⋅10 7 y n ≤ 200. Ken Takusagawa enumeró expansiones hasta s 9 Archivado el 25 de diciembre de 2014 en Wayback Machine y expansiones s 10 Archivado el 25 de diciembre de 2014 en Wayback Machine . Las expansiones restantes se toman de la lista de expansiones de la serie Sylvester . Archivado el 29 de noviembre de 2014 en Wayback Machine , mantenido por Jens Kruse Andersen. A partir del 13/06/2014.
↑ En su artículo, Seiden y Voginger se refieren a la secuencia de Sylvester como la "secuencia de Salzer", basándose en el trabajo de Salzer ( Salzer 1947 ) en la aproximación más cercana.
↑ Domaratzki, Ellul, Shallit, Wang, 2005 .

Literatura

Catalina Badea. Un teorema sobre la irracionalidad de series infinitas y aplicaciones // Acta Arithmetica . - 1993. - T. 63 . - S. 313-323 .
Badea, Catalán. Sobre algunos criterios de irracionalidad para series de racionales positivos: una encuesta (inglés) . — 1995.
Charles P. Boyer, Krzysztof Galicki, János Kollár. Métricas de Einstein sobre esferas // Annals of Mathematics . - 2005. - T. 162 , núm. 1 . - S. 557-580 . - doi : 10.4007/annals.2005.162.557 . — arXiv : matemáticas.DG/0309408 .
Lawrence Breton, Richard Hill. Sobre la ecuación diofántica 1=Σ1/ n i + 1/Π n i y una clase de singularidades superficiales complejas homólogamente triviales // Pacific Journal of Mathematics . - 1988. - T. 133 , núm. 1 . - S. 41-67 . -doi : 10.2140 / pjm.1988.133.41 .
DJ Marrón. Un límite inferior para los algoritmos de empaquetado de contenedores unidimensionales en línea. — Laboratorio de Ciencias Coordinadas, Univ. de Illinois, Urbana-Champaign, 1979. - vol. tecnología Reps. R-864 .
D. R. Curtis. Sobre el problema diofántico de Kellogg // American Mathematical Monthly . - 1922. - T. 29 , núm. 10 _ - S. 380-387 . -doi : 10.2307/ 2299023 . — .
Michael Domaratzki, Keith Ellul, Jeffrey Shallit, Ming-Wei Wang. No unicidad y radio de NFA unarios cíclicos // Revista internacional de fundamentos de informática. - 2005. - T. 16 , núm. 5 . - S. 883-896 . -doi : 10.1142/ S0129054105003352 .
Paul Erdös, Ronald L. Graham. Viejos y nuevos problemas y resultados en teoría combinatoria de números. — Monografías de L'Enseignement Mathematique, no. 28, Universidad. de Ginebra, 1980.
Gábor Galambos, Gerhard J. Woeginger. Embalaje en contenedores en línea: una encuesta restringida // Métodos matemáticos de investigación operativa. - 1995. - vol. 42 , edición. 1 . — Pág. 25 . -doi : 10.1007/ BF01415672 .
Salomón W. Golomb. Sobre ciertas secuencias recurrentes no lineales // American Mathematical Monthly. - 1963. - T. 70 , núm. 4 . - S. 403-405 . -doi : 10.2307/ 2311857 . . _
R. Graham, DE Knuth, O. Patashnik. Matemáticas Concretas. — 2do. - Addison-Wesley, 1989. - ISBN 0-201-55802-5 .
Richard K Guy. Problemas no resueltos en teoría de números. — 3er. - Springer-Verlag , 2004. - Pág. 346. - ISBN 0-387-20860-7 .
Richard Guy, Richard Nowakowski. Descubriendo números primos con Euclid // Delta (Waukesha). - 1975. - V. 5 , núm. 2 . - S. 49-63 .
Rafe Jones. La densidad de divisores primos en la dinámica aritmética de polinomios cuadráticos . - 2006. - arXiv : matemáticas.NT/0612415 .
Frank M.Liang. Un límite inferior para el embalaje en contenedores en línea // Cartas de procesamiento de información. - 1980. - T. 10 , núm. 2 . - S. 76-79 . - doi : 10.1016/S0020-0190(80)90077-0 .
GA Miller. Grupos que poseen un pequeño número de conjuntos de operadores conjugados // Transacciones de la American Mathematical Society . - 1919. - Vol. 20 , edición. 3 . - P. 260-270 . -doi : 10.2307/ 1988867 . — .
RWK Odoni. Sobre los divisores primos de la sucesión w n+1 =1+w 1 ⋯ w n // J. Lond. Matemáticas. Soc., II. Ser.. - 1985. - T. 32 . - S. 1-11 .
Martin Rosenman, F. Underwood. Problema 3536 // American Mathematical Monthly. - 1933. - T. 40 , núm. 3 . - S. 180-181 . — .
S. E. Salzer. La aproximación de números como sumas de recíprocos // American Mathematical Monthly. - 1947. - T. 54 , núm. 3 . - S. 135-142 . -doi : 10.2307/ 2305906 . — .
Steven S. Seiden, Gerhard J. Woeginger. Revisión del problema del material de corte bidimensional // Programación matemática. - 2005. - T. 102 , núm. 3 . - S. 519-530 . -doi : 10.1007/ s10107-004-0548-1 .
K. Soundarajan. Aproximar 1 desde abajo usando n fracciones egipcias. - 2005. - arXiv : math.CA/0502247 .
JJ Silvestre. Sobre un punto en la teoría de las fracciones vulgares // American Journal of Mathematics . - 1880. - T. 3 , núm. 4 . - S. 332-335 . -doi : 10.2307/ 2369261 . — .
Ilán Vardi. Recreaciones computacionales en Mathematica. - Addison-Wesley, 1991. - S. 82-89. - ISBN 0-201-52989-0 .

Enlaces

Irracionalidad de las sumas cuadráticas , de MathPages de KS Brown.
Weisstein, Eric W. Sylvester's Sequence (inglés) en el sitio web de Wolfram MathWorld .