En teoría de números , la secuencia de Sylvester es una secuencia entera en la que cada término de la secuencia es el producto de los términos anteriores, más uno. Los primeros términos de la secuencia son
- 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (secuencia A000058 en la OEIS ).
La secuencia de Sylvester lleva el nombre de James Joseph Sylvester , quien la investigó por primera vez en 1880. Sus valores crecen doblemente exponencialmente , 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 con la misma número de términos. 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, pero, debido al rápido crecimiento de la secuencia, las factorizaciones primas completas se conocen solo para algunos de sus términos. Los valores derivados de esta secuencia también se han utilizado para construir representaciones de fracciones egipcias finitas de 1, variedades de Sasakian Einstein e instancias difíciles para algoritmos en línea .
Definiciones formales
Formalmente, la secuencia de Sylvester se puede definir mediante la fórmula
El producto del conjunto vacío es 1, entonces s 0 = 2.
Alternativamente, se puede definir la secuencia por la recurrencia
- con s 0 = 2.
Es sencillo demostrar por inducción que esto es equivalente a la otra definición.
Fórmula de forma cerrada y asintóticas
Los números de Sylvester crecen doblemente exponencialmente en función de n . Específicamente, se puede demostrar que
para un número E que es aproximadamente 1,26408473530530 ... [1] (secuencia A076393 en la OEIS ). Esta fórmula tiene el efecto del siguiente algoritmo :
- s 0 es el número entero más cercano a E 2 ; s 1 es el número entero más cercano a E 4 ; s 2 es el número entero más cercano a E 8 ; para s n , tome E 2 , eleve al cuadrado n más veces y obtenga el entero más cercano.
Este solo sería un algoritmo práctico si tuviéramos una mejor manera de calcular E para el número requerido de lugares que calcular s n y sacar su raíz cuadrada repetida .
El crecimiento doble exponencial de la secuencia de Sylvester no es sorprendente si se compara con la secuencia de números de Fermat F n ; los números de Fermat suelen definirse 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:
Conexión con fracciones egipcias
Las fracciones unitarias formadas por los recíprocos de los valores en la secuencia de Sylvester generan una serie infinita :
Las sumas parciales de esta serie tienen una forma simple,
Esto puede demostrarse por inducción, o más directamente al señalar que la recursividad implica que
así que la suma telescopios
Dado que esta secuencia de sumas parciales ( s j - 2) / ( s j - 1) converge en uno, la serie general forma una representación de fracción egipcia infinita del número uno:
Se pueden encontrar representaciones de fracciones egipcias finitas de una, de cualquier longitud, truncando esta serie y restando una del último denominador:
La suma de los primeros k términos de la serie infinita proporciona la subestimación más cerca posible de 1 por cualquier k fracción egipcia -term. [2] Por ejemplo, los primeros cuatro términos se suman a 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 secuencia de Sylvester como el resultado de un algoritmo codicioso para fracciones egipcias , que en cada paso elige el denominador más pequeño posible que hace que la suma parcial de la serie sea menor que uno. Alternativamente, los términos de la secuencia después de la primera pueden verse como los denominadores de la extraña expansión codiciosa de 1/2.
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, al mismo tiempo que tiene una serie de recíprocos que convergen en un número racional . Esta secuencia proporciona un ejemplo que muestra que el crecimiento doble exponencial no es suficiente para hacer que una secuencia entera sea una secuencia irracional . [3]
Para hacer esto más preciso, se sigue de los resultados de Badea (1993) que, si una secuencia de enteros crece lo suficientemente rápido que
y si la serie
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
que se puede utilizar para definir la secuencia de Sylvester.
Erdős & 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,
Badea (1995) analiza los avances relacionados con esta conjetura; véase también Brown (1979) .
Divisibilidad y factorizaciones
Si i < j , se sigue 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 relativos . La secuencia se puede usar 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 puede usarse para probar que hay infinitos números primos congruentes con 7 módulo 12. [4]
¿Están todos los términos en la secuencia de Sylvester libres de cuadrados?
Aún se desconoce mucho sobre la factorización de los números en la secuencia de Sylvester. Por ejemplo, no se sabe si todos los números de la secuencia son libres de cuadrados , aunque todos los términos conocidos lo son.
Como describe Vardi (1991) , es fácil determinar qué número de Sylvester (si lo hay) divide un primo p dado : simplemente calcule la recurrencia definiendo los números módulo p hasta encontrar un número que sea congruente con cero (mod p ) o encontrar un módulo repetido. Usando esta técnica, encontró que 1166 de los primeros tres millones de números primos son divisores de números de Sylvester, [5] y que ninguno de estos números primos tiene un cuadrado que divida un número de Sylvester. El conjunto de primos que pueden ocurrir como factores de los números de Sylvester es de densidad cero en el conjunto de todos los primos: [6] de hecho, el número de dichos primos menores que x es. [7]
La siguiente tabla muestra factorizaciones conocidas de estos números (excepto los primeros cuatro, que son todos primos): [8]
norte | Factores de s n |
---|---|
4 | 13 × 139 |
5 | 3263443, que es primo |
6 | 547 × 607 × 1033 × 31051 |
7 | 29881 × 67003 × 9119521 × 6212157481 |
8 | 5295435634831 × 31401519357481261 × 77366930214021991992277 |
9 | 181 × 1987 × 112374829138729 × 114152531605972711 × 35874380272246624152764569191134894955972560447869169859142453622851 |
10 | 2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156 |
11 | 73 × C416 |
12 | 2589377038614498251653 × 2872413602289671035947763837 × C785 |
13 | 52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600 |
14 | 13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293 |
15 | 17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618 |
dieciséis | 128551 × C13335 |
17 | 635263 × 1286773 × 21269959 × C26661 |
18 | 50201023123 × 139263586549 × 60466397701555612333765567 × C53313 |
19 | 775608719589345260583891023073879169 × C106685 |
20 | 352867 × 6210298470888313 × C213419 |
21 | 387347773 × 1620516511 × C426863 |
22 | 91798039513 × C853750 |
Como es habitual, P n y C n denotan números primos y números compuestos de n dígitos.
Aplicaciones
Boyer, Galicki y Kollár (2005) utilizan las propiedades de la secuencia de Sylvester para definir un gran número de variedades de Sasakian Einstein que tienen la topología diferencial de esferas de dimensiones impares o esferas exóticas . Muestran que el número de métricas distintas 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, tiene un crecimiento exponencial doble con n .
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 empaquetado de contenedores en línea . Seiden y Woeginger (2005) utilizan de manera similar la secuencia para limitar el rendimiento de un algoritmo de material de corte bidimensional. [9]
El problema de Znám se refiere a conjuntos de números tales que cada número del conjunto se 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 para la clasificación de singularidades superficiales (Brenton y Hill 1988) y para la teoría de los autómatas finitos no deterministas . [10]
DR Curtiss ( 1922 ) describe una aplicación de las aproximaciones más cercanas a sumas de fracciones unitarias de uno por k -término, en el límite inferior del número de divisores de cualquier número perfecto , y Miller (1919) usa la misma propiedad para el límite superior del tamaño de ciertos grupos .
Ver también
- Constante de Cahen
- Número pseudoperfecto primario
- Número de leonardo
Notas
- ↑ Graham, Knuth & Patashnik (1989) establecieron esto como un ejercicio; véase también Golomb (1963) .
- ↑ Esta afirmación se atribuye comúnmente a Curtiss (1922) , pero Miller (1919) parece estar haciendo la misma afirmación en un artículo anterior. Véase también Rosenman y Underwood (1933) , Salzer (1947) y Soundararajan (2005) .
- ↑ Guy (2004) .
- ^ Guy y Nowakowski (1975) .
- ^ Esto parece ser un error tipográfico, ya que Andersen encuentra 1167 divisores primos en este rango.
- ^ Jones (2006) .
- ^ Odoni (1985) .
- ^ Todos los factores primos p de números Sylvester s n con p <5 × 10 7 y n ≤ 200 están listados por Vardi. Ken Takusagawa enumera las factorizaciones hasta s 9 y la factorización de s 10 . Las factorizaciones restantes son de una lista de factorizaciones de la secuencia de Sylvester mantenida por Jens Kruse Andersen. Consultado el 13 de junio de 2014.
- ↑ En su trabajo, Seiden y Woeginger se refieren a la secuencia de Sylvester como "secuencia de Salzer" después del trabajo de Salzer (1947) sobre la aproximación más cercana.
- ^ Domaratzki y col. (2005) .
Referencias
- Badea, Catalin (1993). "Un teorema sobre la irracionalidad de series y aplicaciones infinitas" . Acta Arithmetica . 63 (4): 313–323. doi : 10.4064 / aa-63-4-313-323 . Señor 1218459 .
- Badea, Catalin (1995). "Sobre algunos criterios de irracionalidad para una serie de racionales positivos: una encuesta" (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". Annals of Mathematics . 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). "En la ecuación diofántica 1 = Σ1 / n i + 1 / Π n i y una clase de singularidades superficiales complejas homológicamente triviales" . Pacific Journal of Mathematics . 133 (1): 41–67. doi : 10.2140 / pjm.1988.133.41 . Señor 0936356 .
- Brown, DJ (1979). "Un límite inferior para los algoritmos de empaquetado de contenedores unidimensionales en línea". Tech. Rep. R-864. Laboratorio de Ciencias Coordinado., Univ. de Illinois, Urbana-Champaign. Cite journal requiere
|journal=
( ayuda ) - 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; Lo haré, Jeffrey ; Wang, Ming-Wei (2005). "No unicidad y radio de NFA unarios cíclicos" . Revista Internacional de Fundamentos de la Ciencia de la Computación . 16 (5): 883–896. doi : 10.1142 / S0129054105003352 . Señor 2174328 .
- Erdős, Paul ; Graham, Ronald L. (1980). Problemas y resultados antiguos y nuevos en la teoría combinatoria de números . Monografías de L'Enseignement Mathématique, No. 28, Univ. de Genève. Señor 0592420 .
- Galambos, Gábor; Woeginger, Gerhard J. (1995). "Embalaje de contenedores en línea - Una encuesta restringida". Métodos matemáticos de investigación operativa . 42 (1): 25. doi : 10.1007 / BF01415672 . Señor 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 . Señor 0148605 .
- Graham, R .; Knuth, DE ; Patashnik, O. (1989). Matemáticas concretas (2ª ed.). Addison-Wesley. Ejercicio 4.37. ISBN 0-201-55802-5.
- Guy, Richard K. (2004). "Secuencias de irracionalidad E24". Problemas no resueltos en teoría de números (3ª ed.). Springer-Verlag . pag. 346. ISBN 0-387-20860-7. Zbl 1058.11001 .
- Guy, Richard; Nowakowski, Richard (1975). "Descubriendo primos con Euclid". Delta (Waukesha) . 5 (2): 49–63. Señor 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 : matemáticas.NT / 0612415 . Bibcode : 2006math ..... 12415J . doi : 10.1112 / jlms / jdn034 . S2CID 15310955 .
- Liang, Frank M. (1980). "Un límite inferior para el embalaje de contenedores en línea". Cartas de procesamiento de información . 10 (2): 76–79. doi : 10.1016 / S0020-0190 (80) 90077-0 . Señor 0564503 .
- Miller, GA (1919). "Grupos que poseen un pequeño número de conjuntos de operadores conjugados" . Transacciones de la American Mathematical Society . 20 (3): 260–270. doi : 10.2307 / 1988867 . JSTOR 1988867 .
- Odoni, RWK (1985). "En los divisores primos de la secuencia w n + 1 = 1 + w 1 ⋯ 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 . Señor 0020339 .
- Seiden, Steven S .; Woeginger, Gerhard J. (2005). "El problema del material de corte bidimensional revisado". Programación matemática . 102 (3): 519–530. doi : 10.1007 / s10107-004-0548-1 . Señor 2136225 . S2CID 35815524 .
- Soundararajan, K. (2005). "Aproximadamente 1 desde abajo usando n fracciones egipcias". arXiv : matemáticas.CA / 0502247 . Cite journal requiere
|journal=
( ayuda ) - Sylvester, JJ (1880). "En un punto de la teoría de las fracciones vulgares". Revista Estadounidense de Matemáticas . 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. "Secuencia de Sylvester" . MathWorld .