En matemáticas , los números de Ulam comprenden una secuencia entera ideada y nombrada en honor a Stanislaw Ulam , quien la introdujo en 1964. [1] La secuencia estándar de Ulam (la secuencia (1, 2) -Ulam) comienza con U 1 = 1 y U 2 = 2. Entonces, para n > 2, U n se define como el número entero más pequeño que es la suma de dos términos anteriores distintos exactamente de una manera y más grande que todos los términos anteriores.
Ejemplos de
Como consecuencia de la definición, 3 es un número Ulam (1 + 2); y 4 es un número Ulam (1 + 3). (Aquí 2 + 2 no es una segunda representación de 4, porque los términos anteriores deben ser distintos). El entero 5 no es un número Ulam, porque 5 = 1 + 4 = 2 + 3. Los primeros términos son
- 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114, 126, 131, 138, 145, 148, 155, 175, 177, 180, 182, 189, 197, 206, 209, 219, 221, 236, 238, 241, 243, 253, 258, 260, 273, 282, ... (secuencia A002858 en la OEIS ).
Hay infinitos números Ulam. Porque, después de que ya se hayan determinado los primeros n números de la secuencia, siempre es posible extender la secuencia en un elemento más: U n −1 + U n se representa de forma única como una suma de dos de los primeros n números, y Puede haber otros números más pequeños que también se representan de forma única de esta manera, por lo que el siguiente elemento puede elegirse como el más pequeño de estos números representables de forma única. [2]
Se dice que Ulam conjeturó que los números tienen densidad cero , [3] pero parecen tener una densidad de aproximadamente 0,07398. [4]
Propiedades
Aparte de 1 + 2 = 3, cualquier número Ulam posterior no puede ser la suma de sus dos números Ulam consecutivos anteriores.
- Prueba: Suponga que para n > 2, U n −1 + U n = U n +1 es la suma requerida de una sola manera, entonces U n −2 + U n produce una suma de una sola manera y cae entre U n y U n +1 . Esto contradice la condición de que U n +1 es el siguiente número Ulam más pequeño. [5]
Para n > 2, cualesquiera tres números Ulam consecutivos ( U n −1 , U n , U n +1 ) como lados enteros formarán un triángulo. [6]
- Prueba: La propiedad anterior establece que para n > 2, U n −2 + U n ≥ U n + 1 . En consecuencia, U n −1 + U n > U n +1 y debido a que U n −1 < U n < U n +1 se satisface la desigualdad del triángulo .
La secuencia de números de Ulam forma una secuencia completa .
- Prueba: Por definición, U n = U j + U k donde j < k < ny es el entero más pequeño que es la suma de dos números Ulam más pequeños distintos de exactamente una manera. Esto significa que para todo U n con n > 3, el mayor valor que U j puede tener es U n −3 y el mayor valor que U k puede tener es U n −1 . [5] [7]
- Por tanto, U n ≤ U n −1 + U n −3 <2 U n −1 y U 1 = 1, U 2 = 2, U 3 = 3. Esta es una condición suficiente para que los números de Ulam sean una secuencia completa.
Para cada entero n > 1 siempre hay al menos un número Ulam U j tal que n ≤ U j <2 n .
- Prueba: Se ha demostrado que hay infinitos números Ulam y comienzan en 1. Por lo tanto, para cada entero n > 1 es posible encontrar j tal que U j −1 ≤ n ≤ U j . De la demostración anterior para n > 3, U j ≤ U j −1 + U j −3 <2 U j −1 . Por lo tanto n ≤ U j < 2U j −1 ≤ 2 n . También para n = 2 y 3 la propiedad es verdadera por cálculo.
En cualquier secuencia de 5 números enteros positivos consecutivos { i , i + 1, ..., i + 4}, i > 4 puede haber un máximo de 2 números Ulam. [7]
- Prueba: Suponga que la secuencia { i , i + 1, ..., i + 4} tiene su primer valor i = U j un número Ulam, entonces es posible que i + 1 sea el próximo número Ulam U j +1 . Ahora considere i + 2, este no puede ser el próximo número de Ulam U j +2 porque no es una suma única de dos términos anteriores. yo + 2 = U j +1 + U 1 = U j + U 2 . Existe un argumento similar para i + 3 e i + 4.
Desigualdades
Los números de Ulam son pseudoaleatorios y demasiado irregulares para tener límites estrechos. Sin embargo, a partir de las propiedades anteriores, es decir, en el peor de los casos, el siguiente número de Ulam U n +1 ≤ U n + U n −2 y en cualesquiera cinco enteros positivos consecutivos como máximo dos pueden ser números de Ulam, se puede afirmar que
- 5/2n −7 ≤ U n ≤ N n +1 para n > 0, [7]
donde N n son los números en la secuencia de las vacas de Narayana : 1,1,1,2,3,4,6,9,13,19, ... con la relación de recurrencia N n = N n −1 + N n −3 que comienza en N 0 .
Estructura oculta
Se ha observado [8] que los primeros 10 millones de números Ulam satisfacen excepto por los cuatro elementos (esto ahora se ha verificado por primera vez Números de Ulam). Las desigualdades de este tipo suelen ser ciertas para las secuencias que presentan alguna forma de periodicidad, pero la secuencia de Ulam no parece ser periódica y el fenómeno no se comprende. Se puede aprovechar para hacer un cálculo rápido de la secuencia de Ulam (ver # Enlaces externos ).
Generalizaciones
La idea se puede generalizar como números ( u , v ) -Ulam seleccionando diferentes valores iniciales ( u , v ). Una secuencia de números ( u , v ) -Ulam es regular si la secuencia de diferencias entre números consecutivos en la secuencia es eventualmente periódica. Cuando v es un número impar mayor que tres, los números (2, v ) -Ulam son regulares. Cuando v es congruente con 1 (mod 4) y al menos cinco, los números (4, v ) -Ulam vuelven a ser regulares. Sin embargo, los números de Ulam en sí mismos no parecen ser regulares. [9]
Se dice que una secuencia de números es s - aditiva si cada número en la secuencia, después de los términos iniciales de 2 s de la secuencia, tiene exactamente s representaciones como una suma de dos números anteriores. Por lo tanto, los números Ulam y los números ( u , v ) -Ulam son secuencias aditivas 1. [10]
Si una secuencia se forma agregando el número más grande con una representación única como una suma de dos números anteriores, en lugar de agregar el número más pequeño representable de forma única, entonces la secuencia resultante es la secuencia de números de Fibonacci . [11]
Notas
- ↑ Ulam ( 1964a , 1964b ).
- ↑ Recaman (1973) ofrece un argumento similar, expresado como prueba por contradicción . Afirma que, si hubiera un número finito de Ulam, entonces la suma de los dos últimos también sería un número Ulam, una contradicción. Sin embargo, aunque la suma de los dos últimos números tendría en este caso una representación única como una suma de dos números Ulam, no sería necesariamente el número más pequeño con una representación única.
- ↑ La afirmación de que Ulam hizo esta conjetura está en OEIS OEIS : A002858 , pero Ulam no aborda la densidad de esta secuencia en Ulam (1964a) , y en Ulam (1964b) plantea la cuestión de determinar su densidad sin conjeturar un valor para eso. Recaman (1973) repite la pregunta de Ulam (1964b) sobre la densidad de esta secuencia, nuevamente sin conjeturar un valor para ella.
- ^ OEIS OEIS : A002858
- ↑ a b Recaman (1973)
- ^ OEIS OEIS : A330909
- ↑ a b c Philip Gibbs y Judson McCranie (2017). "Los números de Ulam hasta un billón" . pag. 1. Introducción).
- ↑ Steinerberger (2015)
- ↑ Queneau (1972) observó por primera vez la regularidad de las secuencias para u = 2 yv = 7 yv = 9. Finch (1992) conjeturó la extensión de este resultado a todos los v imparesmayores que tres, y esta conjetura fue probada por Schmerl Y Spiegel (1994) . La regularidad de losnúmeros(4, v ) -Ulam fue probada por Cassaigne & Finch (1995) .
- ^ Queneau (1972) .
- ^ Finch (1992) .
Referencias
- Cassaigne, Julien; Finch, Steven R. (1995), "Una clase de secuencias aditivas y recurrencias cuadráticas" , Matemáticas experimentales , 4 (1): 49–60, doi : 10.1080 / 10586458.1995.10504307 , MR 1359417
- Finch, Steven R. (1992), "Sobre la regularidad de ciertas secuencias 1-aditivas", Journal of Combinatorial Theory, Serie A , 60 (1): 123-130, doi : 10.1016 / 0097-3165 (92) 90042- S , MR 1156652
- Guy, Richard (2004), Problemas no resueltos en teoría de números (3ª ed.), Springer-Verlag , págs. 166-167, ISBN 0-387-20860-7
- Queneau, Raymond (1972), "Sur les suites s -additives", Journal of Combinatorial Theory, Serie A (en francés), 12 (1): 31–71, doi : 10.1016 / 0097-3165 (72) 90083-0 , MR 0302597
- Recaman, Bernardo (1973), "Preguntas sobre una secuencia de Ulam", American Mathematical Monthly , 80 (8): 919–920, doi : 10.2307 / 2319404 , JSTOR 2319404 , MR 1537172
- Schmerl, James; Spiegel, Eugene (1994), "La regularidad de algunas secuencias 1-aditivas", Journal of Combinatorial Theory, Serie A , 66 (1): 172-175, doi : 10.1016 / 0097-3165 (94) 90058-2 , MR 1273299
- Ulam, Stanislaw (1964a), "Análisis combinatorio en conjuntos infinitos y algunas teorías físicas", SIAM Review , 6 (4): 343–355, doi : 10.1137 / 1006090 , JSTOR 2027963 , MR 0170832
- Ulam, Stanislaw (1964b), Problemas en matemáticas modernas , Nueva York: John Wiley & Sons, Inc, p. xi, MR 0280310
- Steinerberger, Stefan (2015), A Hidden Signal in the Ulam sequence , Experimental Mathematics, arXiv : 1507.00267 , Bibcode : 2015arXiv150700267S
enlaces externos
- Secuencia Ulam de MathWorld
- Cálculo rápido de la secuencia de Ulam por Philip Gibbs
- Descripción del algoritmo por Donald Knuth
- La página de github de Daniel Ross