Secuencia de Moser-de Bruijn

Número, suma de potencias distintas de 4

La tabla de adición para donde y ambos pertenecen a la secuencia de Moser-de Bruijn, y la curva de orden Z que conecta las sumas en orden numérico ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$

En teoría de números , la secuencia de Moser-de Bruijn es una secuencia de números enteros que lleva el nombre de Leo Moser y Nicolaas Govert de Bruijn , que consiste en las sumas de distintas potencias de 4. Equivalentemente, son los números cuyas representaciones binarias son distintas de cero solo en posiciones pares.

Los números de Moser–de Bruijn en esta secuencia crecen en proporción a los números cuadrados . Son los cuadrados de una forma modificada de aritmética sin llevar . La diferencia de dos números de Moser–de Bruijn, multiplicada por dos, nunca es cuadrada. Cada número natural se puede formar de una manera única como la suma de un número de Moser–de Bruijn y dos veces un número de Moser–de Bruijn. Esta representación como suma define una correspondencia uno a uno entre números enteros y pares de números enteros, enumerados en orden de sus posiciones en una curva de orden Z.

La sucesión de Moser-de Bruijn se puede utilizar para construir pares de números trascendentales que son inversos multiplicativos entre sí y ambos tienen representaciones decimales simples. Una relación de recurrencia simple permite calcular los valores de la sucesión de Moser-de Bruijn a partir de valores anteriores y se puede utilizar para demostrar que la sucesión de Moser-de Bruijn es una sucesión 2-regular .

Definición y ejemplos

Los números de la secuencia de Moser–de Bruijn se forman sumando distintas potencias de 4. La secuencia enumera estos números en orden ordenado; comienza ^[1]

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 ₂ tiene dígitos distintos de cero en las posiciones de 2 ⁶ , 2 ² y 2 ⁰ , todas las cuales tienen exponentes pares. Los números en la secuencia también pueden describirse 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 los dígitos binarios en posiciones impares, que deberían ser todos cero. La representación hexadecimal de estos números contiene solo los dígitos 0, 1, 4, 5. Por ejemplo, 69 = 1011 ₄ = 45 ₁₆ . Equivalentemente, son los números cuyas representaciones binarias y negabinarias son iguales. ^{[1] [2]} Debido a que no hay dos números distintos de cero consecutivos en sus representaciones binarias, la secuencia de Moser–de Bruijn forma una subsecuencia de los números fibinarios .

Tasa de crecimiento y diferencias

Gráfico del número de elementos de secuencia hasta dividido por , en una escala horizontal logarítmica ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$

De las definiciones binarias o de base 4 de estos números se desprende que crecen aproximadamente en proporción a los números cuadrados . El número de elementos en la secuencia de Moser-de Bruijn que están por debajo de cualquier umbral dado es proporcional a , ^[3] un hecho que también es cierto para los números cuadrados. Más precisamente, el número oscila entre (para números de la forma ) y (para ). De hecho, los números en la secuencia de Moser-de Bruijn son los cuadrados para una versión de aritmética sin llevar a cabo números binarios, en la que la adición y la multiplicación de bits individuales son respectivamente las operaciones de conjunción lógica o exclusiva y . ^[4] ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n=4^{k}}$ ${\displaystyle {\sqrt {3n}}}$ ${\displaystyle n\sim 4^{k}/3}$

En relación con el teorema de Furstenberg–Sárközy sobre secuencias de números sin diferencia al cuadrado, Imre Z. Ruzsa encontró una construcción para grandes conjuntos libres de diferencias al cuadrado que, como la definición binaria de la secuencia de Moser–de Bruijn, restringe los dígitos en posiciones alternas en los números base. ^[5] Cuando se aplica a la base , la construcción de Ruzsa genera la secuencia de Moser–de Bruijn multiplicada por dos, un conjunto que nuevamente es libre de diferencias al cuadrado. Sin embargo, este conjunto es demasiado disperso para proporcionar límites inferiores no triviales para el teorema de Furstenberg–Sárközy. ${\displaystyle b}$ ${\displaystyle b=2}$

Representación única como sumas

La sucesión de Moser–de Bruijn obedece a una propiedad similar a la de una sucesión de Sidón : las sumas , donde y ambas pertenecen a la sucesión de Moser–de Bruijn, son todas únicas. No hay dos de estas sumas que tengan el mismo valor. Además, cada entero puede representarse como una suma , donde y ambas pertenecen a la sucesión de Moser–de Bruijn. Para encontrar la suma que representa , calcule , el booleano bit a bit y de con un valor binario (expresado aquí en hexadecimal ) que tenga unos en todas sus posiciones pares, y establezca . ^{[1] [6]} ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x=n\ \&\ \mathrm {0x55555555} }$ ${\displaystyle n}$ ${\displaystyle y=(n-x)/2}$

La sucesión de Moser-de Bruijn es la única sucesión con esta propiedad, que todos los números enteros tienen una expresión única como . Es por esta razón que la sucesión fue estudiada originalmente por Moser (1962). ^[7] Extendiendo la propiedad, De Bruijn (1964) encontró infinitas otras expresiones lineales como esa, cuando y ambos pertenecen a la sucesión de Moser-de Bruijn, representan de manera única todos los números enteros. ^{[8] [9]} ${\displaystyle x+2y}$ ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$

Curva de orden Z y fórmula sucesora

Al descomponer un número en , y luego aplicar a y una función que preserva el orden de la secuencia de Moser–de Bruijn a los números enteros (reemplazando las potencias de cuatro en cada número por las potencias de dos correspondientes), se obtiene una biyección de números enteros no negativos a pares ordenados de números enteros no negativos. La inversa de esta biyección da un ordenamiento lineal en los puntos del plano con coordenadas de números enteros no negativos, que se puede utilizar para definir la curva de orden Z . ^{[1] [10]} ${\displaystyle n}$ ${\displaystyle n=x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$

En relación con esta aplicación, es conveniente tener una fórmula para generar cada elemento sucesivo de la secuencia de Moser–de Bruijn a partir de su predecesor. Esto se puede hacer de la siguiente manera. Si es un elemento de la secuencia, entonces el siguiente miembro después se puede obtener rellenando los bits en posiciones impares de la representación binaria de por uno, sumando uno al resultado y luego enmascarando los bits rellenados. Rellenar los bits y sumar uno se puede combinar en una sola operación de suma. Es decir, el siguiente miembro es el número dado por la fórmula ^{[1] [6] [10]} Las dos constantes hexadecimales que aparecen en esta fórmula se pueden interpretar como los números 2-ádicos y , respectivamente. ^[1] ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ $${\displaystyle \displaystyle (x+{\textrm {0xaaaaaaab}})\ \&\ {\textrm {0x55555555}}.}$$ ${\displaystyle 1/3}$ ${\displaystyle -1/3}$

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 retirar monedas de una pila de monedas. En cada movimiento, un jugador puede retirar cualquier número de monedas que pertenezca a la secuencia de Moser–de Bruijn. No se permite retirar 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 mover está perdiendo) son exactamente las posiciones de la forma donde pertenece a la secuencia de Moser–de Bruijn. Una estrategia ganadora para jugar a este juego es descomponer el número actual de monedas, , en donde y ambos pertenecen a la secuencia de Moser–de Bruijn, y luego (si es distinto de cero) retirar monedas, dejando una posición fría para el otro jugador. Si es cero, esta estrategia no es posible y no hay movimiento ganador. ^[3] ${\displaystyle n}$ ${\displaystyle 2y}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x+2y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$

Recíprocos decimales

La sucesión de Moser-de Bruijn constituye la base de un ejemplo de un número irracional con la propiedad inusual de que las representaciones decimales de y pueden escribirse de manera simple y explícita. Sea la sucesión de Moser-de Bruijn misma la que denotemos. Entonces, para un número decimal cuyos dígitos distintos de cero están en las posiciones dadas por la sucesión de Moser-de Bruijn, se deduce que los dígitos distintos de cero de su recíproco están ubicados en las posiciones 1, 3, 9, 11, ..., dadas al duplicar los números en y sumar uno a todos ellos: ^{[11] [12]} ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle 1/x}$ ${\displaystyle E}$ $${\displaystyle x=3\sum _{n\in E}10^{-n}=3.300330000000000330033\dots ,}$$ ${\displaystyle E}$ $${\displaystyle {\frac {1}{x}}=3\sum _{n\in E}10^{-2n-1}=0.30300000303\dots \ .}$$

Alternativamente, se puede escribir: $${\displaystyle \displaystyle \left(\sum _{n\in E}10^{-n}\right)\left(\sum _{n\in E}10^{-2n}\right)={\frac {10}{9}}.}$$

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 de Moser-de Bruijn, son números trascendentales . Su trascendencia puede demostrarse a partir del hecho de que las largas cadenas de ceros en sus dígitos permiten que se los aproxime con mayor precisión mediante números racionales de lo que permitiría el teorema de Roth si fueran números algebraicos , con una medida de irracionalidad no menor que 3. ^[12]

Función generadora

La función generadora cuyos exponentes en la forma desarrollada están dados por la sucesión de Moser–de Bruijn, obedece a las ecuaciones funcionales ^{[1] [2]} y ^[14]. Por ejemplo, esta función puede utilizarse para describir los dos recíprocos decimales dados anteriormente: uno es y el otro es . El hecho de que sean recíprocos es una instancia de la primera de las dos ecuaciones funcionales. Los productos parciales de la forma producto de la función generadora pueden utilizarse para generar los convergentes de la expansión fraccionaria continua de estos mismos números, así como múltiplos de ellos. ^[11] $${\displaystyle F(x)=\prod _{i=0}^{\infty }(1+x^{4^{i}})=1+x+x^{4}+x^{5}+x^{16}+x^{17}+\cdots ,}$$ $${\displaystyle F(x)F(x^{2})={\frac {1}{1-x}}}$$ $${\displaystyle F(x)=(1+x)F(x^{4}).}$$ ${\displaystyle 3F(1/10)}$ ${\displaystyle {\tfrac {3}{10}}F(1/100)}$

Recurrencia y regularidad

La secuencia de Moser–de Bruijn obedece a una relación de recurrencia que permite determinar el valor n -ésimo de la secuencia (que comienza en ) a partir del valor en la posición : Iterar esta recurrencia permite expresar cualquier subsecuencia de la forma como una función lineal de la secuencia original, lo que significa que la secuencia de Moser–de Bruijn es una secuencia 2-regular . ^[15] ${\displaystyle S(n)}$ ${\displaystyle S(0)=0}$ ${\displaystyle \lfloor n/2\rfloor }$ $${\displaystyle {\begin{aligned}S(2n)&=4S(n)\\S(2n+1)&=4S(n)+1\end{aligned}}}$$ ${\displaystyle S(2^{i}n+j)}$

Véase también

• Secuencia de Stanley y conjunto de Cantor , conjuntos definidos de manera similar utilizando las representaciones de base 3 de sus elementos

Notas

1. Sloane, N. J. A. (ed.), "Secuencia A000695 (secuencia de Moser–De Bruijn)", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
2. Arndt, Jörg (2011), Matters Computational: Ideas, Algorithms, Source Code (PDF) , Springer, págs. 59, 750.
3. Golomb, Solomon W. (1966), "Una investigación matemática de los juegos de "quitar"", Revista de teoría combinatoria , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , MR  0209015.
4. Applegate, David ; LeBrun, Marc; Sloane, NJA (2011), "Aritmética desalentadora" (PDF) , Journal of Integer Sequences , 14 (9): Artículo 11.9.8, 34, arXiv : 1107.1130 , Bibcode :2011arXiv1107.1130A, MR  2859992.
5. Ruzsa, IZ (1984), "Conjuntos de diferencias sin cuadrados", Periodica Mathematica Hungarica , 15 (3): 205–209, doi :10.1007/BF02454169, MR  0756185, S2CID  122624503.
6. 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 se debe ampliar o reducir de la manera obvia para manejar otros tamaños de palabra.
7. Moser, Leo (1962), "Una aplicación de la generación de series", Mathematics Magazine , 35 (1): 37–38, doi :10.1080/0025570X.1962.11975291, JSTOR  2689100, MR  1571147.
8. De Bruijn, NG (1964), "Algunas descomposiciones directas del conjunto de números enteros", Mathematics of Computation , 18 (88): 537–546, doi : 10.2307/2002940 , JSTOR  2002940, MR  0167447.
9. Eigen, SJ; Ito, Y.; Prasad, VS (2004), "Números enteros universalmente malos y los 2-ádicos", Journal of Number Theory , 107 (2): 322–334, doi : 10.1016/j.jnt.2004.04.001 , MR  2072392.
10. Thiyagalingam, Jeyarajan; Beckmann, Olav; Kelly, Paul HJ (septiembre de 2006), "¿El diseño Morton es competitivo todavía para arreglos bidimensionales grandes?" (PDF) , Concurrency and Computation: Practice and Experience , 18 (11): 1509–1539, doi :10.1002/cpe.v18:11, archivado desde el original (PDF) el 29 de marzo de 2017 , consultado el 18 de noviembre de 2016.
11. van der Poorten, AJ (1993), "Fracciones continuas de series de potencias formales" (PDF) , Advances in number theory (Kingston, ON, 1991) , Oxford Sci. Publ., Oxford Univ. Press, Nueva York, págs. 453–466, MR  1368441.
12. Blanchard, André; Mendès France, Michel (1982), "Symétrie et trascendencia", Bulletin des Sciences Mathématiques , 106 (3): 325–335, SEÑOR  0680277. Como lo cita van der Poorten (1993).
13. Bailey, David H .; Borwein, Jonathan M .; Crandall, Richard E .; Pomerance, Carl (2004), "Sobre las expansiones binarias de números algebraicos", Journal de Théorie des Nombres de Bordeaux , 16 (3): 487–518, doi : 10.5802/jtnb.457 , hdl : 1959.13/1037857 , SEÑOR  2144954 , S2CID  122848891Véase en particular la discusión que sigue al Teorema 4.2.
14. Lehmer, DH ; Mahler, K .; van der Poorten, AJ (1986), "Números enteros con dígitos 0 o 1", Mathematics of Computation , 46 (174): 683–689, doi :10.2307/2008006, JSTOR  2008006, MR  0829638.
15. Allouche, Jean-Paul; Shallit, Jeffrey (1992), "El anillo de secuencias k -regulares", Theoretical Computer Science , 98 (2): 163–197, doi :10.1016/0304-3975(92)90001-V, MR  1166363. Ejemplo 13, pág. 188.

Enlaces externos

• Weisstein, Eric W. , "Secuencia Moser-De Bruijn", MathWorld