En teoría de números , la secuencia de Moser-De Bruijn es una secuencia entera que lleva el nombre de Leo Moser y Nicolaas Govert de Bruijn , que consta de las sumas de potencias distintas de 4. Comienza
- 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, ... (secuencia A000695 en la OEIS )
Por ejemplo, 69 pertenece a esta secuencia porque es igual a 64 + 4 + 1, una suma de tres potencias distintas de 4.
Otra definición de la secuencia de Moser-De Bruijn es que es la secuencia ordenada de números cuya representación binaria tiene dígitos distintos de cero solo en las posiciones pares. Por ejemplo, 69 pertenece a la secuencia, porque su representación binaria 1000101 2 tiene dígitos distintos de cero en las posiciones de 2 6 , 2 2 y 2 0 , todos los cuales tienen exponentes pares. Los números en la secuencia también se pueden describir como los números cuya representación en base 4 usa solo los dígitos 0 o 1. [1] Para un número en esta secuencia, la representación en base 4 se puede encontrar a partir de la representación binaria omitiendo el dígitos binarios en posiciones impares, que deberían ser todos cero. Otra forma de verlo es que estos son números cuya representación hexadecimal contiene solo los dígitos 0, 1, 4, 5. Por ejemplo, 69 = 1011 4 = 45 16 .
De manera equivalente, son los números cuyas representaciones binarias y negabinarias son iguales. [1] [2]
De las definiciones binarias o de base 4 de estos números se deduce que crecen aproximadamente en proporción a los números cuadrados . El número de elementos de la secuencia Moser-De Bruijn que están por debajo de un umbral determinado. es proporcional a , [3] un hecho que también es cierto para los números cuadrados. De hecho, los números en la secuencia Moser-De Bruijn son los cuadrados para una versión de la aritmética sin llevar en números binarios, en los que la suma y la multiplicación de bits individuales son, respectivamente, la exclusiva o y conjunción lógica operaciones. [4]
En relación con el teorema de Furstenberg-Sárközy sobre secuencias de números sin diferencia cuadrada, Imre Z. Ruzsa encontró una construcción para conjuntos grandes sin diferencia cuadrada que, como la definición binaria de la secuencia Moser-De Bruijn, restringe los dígitos en posiciones alternas en la base-números. [5] Cuando se aplica a la base, La construcción de Ruzsa genera la secuencia Moser-De Bruijn multiplicada por dos, un conjunto que nuevamente es cuadrado libre de diferencias. Sin embargo, este conjunto es demasiado escaso para proporcionar límites inferiores no triviales para el teorema de Furstenberg-Sárközy.
Representación única como sumas
La secuencia de Moser-De Bruijn obedece a una propiedad similar a la de una secuencia de Sidón : las sumas, dónde y ambos pertenecen a la secuencia Moser-De Bruijn, son todos únicos. No hay dos de estas sumas que tengan el mismo valor. Además, cada entero se puede representar como una suma , dónde y ambos pertenecen a la secuencia Moser-De Bruijn. Para encontrar la suma que representa, calcular , el booleano bit a bit y decon un valor binario (expresado aquí en hexadecimal ) que tiene unos en todas sus posiciones pares, y establece. [1] [6]
La secuencia de Moser-De Bruijn es la única secuencia con esta propiedad, que todos los enteros tienen una expresión única como . Es por esta razón que la secuencia fue originalmente estudiada por Moser (1962) . [7] Ampliando la propiedad, De Bruijn (1964) encontró infinitas otras expresiones lineales como que cuando y ambos pertenecen a la secuencia Moser-De Bruijn, representan de forma única todos los números enteros. [8] [9]
Curva de orden Z y fórmula sucesora
Descomponer un número dentro , y luego aplicar a y un mapa que conserva el orden de la secuencia Moser-De Bruijn a los enteros (reemplazando las potencias de cuatro en cada número por las potencias correspondientes de dos) da una biyección de enteros no negativos a pares ordenados de enteros no negativos. La inversa de esta biyección da una ordenación lineal de los puntos en el plano con coordenadas entero no negativo, que pueden ser utilizados para definir la curva de orden Z . [1] [10]
En relación con esta aplicación, es conveniente tener una fórmula para generar cada elemento sucesivo de la secuencia Moser-De Bruijn a partir de su predecesor. Esto puede hacerse de la siguiente manera. Si es un elemento de la secuencia, luego el siguiente miembro después puede obtenerse completando los bits en posiciones impares de la representación binaria de uno por uno, agregando uno al resultado y luego enmascarando los bits completados. Llenar los bits y agregar uno se puede combinar en una sola operación de adición. Es decir, el siguiente miembro es el número dado por la fórmula
Las dos constantes hexadecimales que aparecen en esta fórmula se pueden interpretar como los números 2-ádicos y , respectivamente. [1]
Juego de resta
Golomb (1966) investigó un juego de resta , análogo a restar un cuadrado , basado en esta secuencia. En el juego de Golomb, dos jugadores se turnan para sacar monedas de una pila demonedas En cada movimiento, un jugador puede retirar cualquier cantidad de monedas que pertenezcan a la secuencia Moser-De Bruijn. No se permite quitar cualquier otro número de monedas. El ganador es el jugador que retira la última moneda. Como observa Golomb, las posiciones "frías" de este juego (aquellas en las que el jugador que está a punto de moverse está perdiendo) son exactamente las posiciones del formulario. dónde pertenece a la secuencia Moser-De Bruijn. Una estrategia ganadora para jugar a este juego es descomponer el número actual de monedas,, dentro dónde y ambos pertenecen a la secuencia Moser-De Bruijn, y luego (si es distinto de cero) para eliminar monedas, dejando una posición fría al otro jugador. Sies cero, esta estrategia no es posible y no hay movimiento ganador. [3]
Recíprocos decimales
La secuencia de Moser-De Bruijn forma la base de un ejemplo de un número irracional con la inusual propiedad de que las representaciones decimales de y pueden escribirse de forma simple y explícita. Dejardenotar la propia secuencia Moser-De Bruijn. Entonces para
un número decimal cuyos dígitos distintos de cero están en las posiciones dadas por la secuencia Moser-De Bruijn, se deduce que los dígitos distintos de cero de su recíproco se ubican en posiciones dadas al duplicar los números en y agregando uno a todos ellos: :
Alternativamente, se puede escribir:
Ejemplos similares también funcionan en otras bases. Por ejemplo, los dos números binarios cuyos bits distintos de cero están en las mismas posiciones que los dígitos distintos de cero de los dos números decimales anteriores también son recíprocos irracionales. [13] Estos números binarios y decimales, y los números definidos de la misma manera para cualquier otra base repitiendo un solo dígito distinto de cero en las posiciones dadas por la secuencia Moser-De Bruijn, son números trascendentales . Su trascendencia puede demostrarse por el hecho de que las largas cadenas de ceros en sus dígitos permiten aproximarlos con números racionales con mayor precisión de lo que permitiría el teorema de Roth si fueran números algebraicos . [12]
Función generadora
La función generadora
cuyos exponentes en la forma expandida están dados por la secuencia de Moser-De Bruijn, obedece a las ecuaciones funcionales
- [1] [2]
y
- [14]
Por ejemplo, esta función se puede utilizar para describir los dos recíprocos decimales dados anteriormente: uno es y el otro es . El hecho de que sean recíprocos es un ejemplo de la primera de las dos ecuaciones funcionales. Los productos parciales de la forma producto de la función generadora se pueden utilizar para generar los convergentes de la expansión fraccionaria continua de estos números, así como sus múltiplos. [11]
Recurrencia y regularidad
La secuencia de Moser-De Bruijn obedece a una relación de recurrencia que permite que el n º valor de la secuencia, (a partir de ) a determinar a partir del valor en la posición :
Iterar esta recurrencia permite cualquier subsecuencia del formulario expresarse como una función lineal de la secuencia original, lo que significa que la secuencia de Moser-De Bruijn es una secuencia regular 2 . [15]
Ver también
- Secuencia de Stanley y conjunto de Cantor , conjuntos definidos de manera similar utilizando las representaciones en base 3 de sus elementos
Notas
- ^ a b c d e f g Sloane, N. J. A. (ed.), "Secuencia A000695 (secuencia Moser-De Bruijn)" , La enciclopedia en línea de secuencias de enteros , Fundación OEIS
- ^ a b Arndt, Jörg (2011), Matters Computational: Ideas, Algorithms, Source Code (PDF) , Springer, págs.59, 750.
- ^ a b Golomb, Solomon W. (1966), "Una investigación matemática de los juegos de" comida para llevar " ", Journal of Combinatorial Theory , 1 (4): 443–458, doi : 10.1016 / S0021-9800 (66) 80016-9 , MR 0209015 CS1 maint: parámetro desalentado ( enlace ).
- ^ Applegate, David ; LeBrun, Marc; Sloane, NJA (2011), "Dismal arithmetic" (PDF) , Journal of Integer Sequences , 14 (9): Artículo 11.9.8, 34, arXiv : 1107.1130 , Bibcode : 2011arXiv1107.1130A , MR 2859992.
- ^ Ruzsa, IZ (1984), "Conjuntos de diferencias sin cuadrados", Periodica Mathematica Hungarica , 15 (3): 205-209, doi : 10.1007 / BF02454169 , MR 0756185 CS1 maint: parámetro desalentado ( enlace ).
- ^ a b Las constantes de esta fórmula se expresan en hexadecimal y se basan en un tamaño de palabra de 32 bits. El mismo patrón de bits debe extenderse o reducirse de la manera obvia para manejar otros tamaños de palabras.
- ^ Moser, Leo (1962), "Una aplicación de la generación de series", Revista de matemáticas , 35 (1): 37–38, JSTOR 2689100 , MR 1571147 CS1 maint: parámetro desalentado ( enlace ).
- ^ De Bruijn, NG (1964), "Algunas descomposiciones directas del conjunto de números enteros", Mathematics of Computation , 18 : 537–546, doi : 10.2307 / 2002940 , MR 0167447 CS1 maint: parámetro desalentado ( enlace ).
- ^ Eigen, SJ; Ito, Y .; Prasad, VS (2004), "Enteros universalmente malos y los 2-adics", Journal of Number Theory , 107 (2): 322–334, doi : 10.1016 / j.jnt.2004.04.001 , MR 2072392.
- ^ a b Thiyagalingam, Jeyarajan; Beckmann, Olav; Kelly, Paul HJ (septiembre de 2006), "¿Es competitivo el diseño de Morton para arreglos bidimensionales grandes?" (PDF) , concurrencia y Cálculo: Practice and Experience , 18 (11): 1509-1539, doi : 10.1002 / cpe.v18: 11 , archivado desde el original (PDF) en 03/29/2017 , recuperados 2016-11- 18.
- ^ a b van der Poorten, AJ (1993), "Fracciones continuas de series formales de potencia" (PDF) , Avances en la teoría de números (Kingston, ON, 1991) , Oxford Sci. Publ., Universidad de Oxford. Press, Nueva York, págs. 453–466, MR 1368441 CS1 maint: parámetro desalentado ( enlace ).
- ^ a b Blanchard, André; Mendès France, Michel (1982), "Symétrie et trascendance", Bulletin des Sciences Mathématiques , 106 (3): 325–335, MR 0680277. Como lo cita van der Poorten (1993) .
- ^ Bailey, David H .; Borwein, Jonathan M .; Crandall, Richard E .; Pomerance, Carl (2004), "Sobre las expansiones binarias de los números algebraicos" , Journal de Théorie des Nombres de Bordeaux , 16 (3): 487–518, doi : 10.5802 / jtnb.457 , MR 2144954. Véase en particular la discusión que sigue al teorema 4.2.
- ^ Lehmer, DH ; Mahler, K .; van der Poorten, AJ (1986), "Enteros con dígitos 0 o 1", Matemáticas de Computación , 46 (174): 683–689, doi : 10.2307 / 2008006 , MR 0829638.
- ^ Allouche, Jean-Paul; Shallit, Jeffrey (1992), "El anillo de k -secuencias regulares ", Ciencias de la computación teóricas , 98 (2): 163-197, doi : 10.1016 / 0304-3975 (92) 90001-V , MR 1166363. Ejemplo 13, pág. 188.
enlaces externos
- Weisstein, Eric W. , "Moser – De Bruijn Sequence" , MathWorld