Generador de Secuencia de Moser-de Bruijn | Calculadora de Potencias de 4

¿Qué es la sucesión de Moser-de Bruijn?

La sucesión de Moser-de Bruijn es una lista de números enteros que se pueden escribir cada uno como suma de potencias distintas de 4. Empieza por 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85 y continúa sin fin. Recibe su nombre de los matemáticos Leo Moser y Nicolaas Govert de Bruijn. En la Enciclopedia en línea de sucesiones de enteros (OEIS) figura con el código A000695.

Un número pertenece a la sucesión exactamente cuando sus dígitos en base 4 son solo 0 y 1, nunca 2 ni 3. Por ejemplo, 21 en base 4 se escribe 111, así que pertenece. El número 22 en base 4 se escribe 112, así que no pertenece.

Fórmula de la sucesión de Moser-de Bruijn

La sucesión puede definirse de tres maneras equivalentes.

Suma de potencias distintas de 4

Un número n pertenece a la sucesión si puede escribirse como

$n = \sum_{i \in S} 4^i$

para algún conjunto S de enteros no negativos, donde cada potencia de 4 se utiliza como máximo una vez.

Prueba de dígitos en base 4

Escribe el número en base 4. Si todos los dígitos son 0 o 1, el número pertenece a la sucesión. Si algún dígito es 2 o 3, no pertenece.

Sustitución de binario a base 4

Contando los términos desde n = 0, el término en el índice n es

$M(n) = \sum_{i=0}^{k} b_i \cdot 4^i$

donde los $b_i$ son los dígitos binarios de n. En otras palabras: escribe n en binario y después interpreta cada dígito binario como un dígito en base 4 en la misma posición. Este es el método que utiliza el generador, ya que solo necesita comprobar bits y sumar números.

Cómo calcular el término n.º

Para hallar M(n), el generador hace lo siguiente para cada índice n, comenzando con n = 0:

1. Observa la forma binaria de n.
2. Por cada bit igual a 1, en la posición j, suma 4^j al total acumulado.
3. Omite los bits iguales a 0.
4. El total acumulado es M(n).

Ejemplo resuelto: M(5)

• 5 en binario es 101.
• El bit 0 (el situado más a la derecha) es 1, así que se suma 4⁰ = 1.
• El bit 1 es 0, así que no se suma nada.
• El bit 2 es 1, así que se suma 4² = 16.
• Total: 1 + 16 = 17.

Por tanto, M(5) = 17. Es el sexto valor que produce el generador, ya que el conteo comienza en M(0).

Ejemplo: primeros 32 términos

Cómo comprobar si un número pertenece a la sucesión

Convierte el número a base 4 y lee sus dígitos.

• 85: en base 4, 85 es 1111 (64 + 16 + 4 + 1). Solo aparecen 0 y 1, por lo que 85 está en la sucesión.
• 90: en base 4, 90 es 1122. Contiene un 2, por lo que 90 no está en la sucesión.

Tasa de crecimiento

La sucesión crece rápidamente, porque cada bit adicional en el índice puede cuadruplicar aproximadamente el valor que aporta. M(19) es 261. M(99) es 5.125. M(999), el término más grande que puede producir este generador, es 349.205. Los términos están cada vez más separados a medida que crece el índice, lo que hace que la sucesión sea dispersa: la mayoría de los números enteros nunca aparecen en ella, aunque tiene infinitos términos.

Cómo usar el generador de la sucesión de Moser-de Bruijn

1. Introduzca el número de términos que desea generar. El campo comienza en 20. Si se borra, no se muestra ningún término hasta que se introduzca un valor nuevo.
2. La lista de términos se actualiza automáticamente, comenzando por M(0).
3. Copia la lista completa con el botón Copiar resultado.

La herramienta acepta números enteros de 1 a 1000. Los valores fuera de ese intervalo, los decimales y las entradas no numéricas muestran un mensaje de validación. Al pedir 20 términos se obtienen de M(0) a M(19); el último valor mostrado es 261. Todo el cálculo se hace en el navegador, por lo que los resultados aparecen de inmediato y no se envía ningún dato a un servidor.

Sucesiones relacionadas

• Potencias de 2 (OEIS A000079): 1, 2, 4, 8, 16, 32, etcétera. Son los componentes básicos de los números binarios ordinarios.
• Sumas de potencias distintas de 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13, etcétera. Es la misma idea que la de la sucesión de Moser-de Bruijn, pero construida en base 3 en lugar de base 4.
• Números fibinarios (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10, etcétera. Son los números cuya forma binaria no tiene dos 1 consecutivos.

Historia

Leo Moser (1921–1970) fue un matemático canadiense de origen austriaco que trabajó en teoría de números. Nicolaas Govert de Bruijn (1918–2012) fue un matemático neerlandés que trabajó en análisis, teoría de números, combinatoria y lógica. La entrada de la OEIS incluye entre sus referencias un artículo de Moser de 1962 en Mathematics Magazine y uno de de Bruijn de 1964 en Mathematics of Computation. Una propiedad clave es que todo entero no negativo n puede escribirse de una sola manera como M(k) + 2·M(l), con M(k) y M(l) tomados de la sucesión.

Preguntas frecuentes

¿Para qué se utiliza la sucesión de Moser-de Bruijn?

Aparece en la teoría aditiva de números, porque todo entero no negativo se descompone de forma única en un término más el doble de otro término. La misma idea de separar bits sustenta las disposiciones de Morton (orden Z), que entrelazan los bits de dos coordenadas. También es un ejercicio sencillo de conversión de bases y de operaciones bit a bit.

¿Cómo se genera la sucesión de Moser-de Bruijn?

Escribe el índice n en binario y después interpreta cada dígito binario como un dígito en base 4 en la misma posición. Para n = 5 (binario 101), se obtiene 4² + 4⁰ = 17.

¿Cómo puedo comprobar si un número pertenece a la sucesión?

Conviértelo a base 4. Si todos los dígitos son 0 o 1, el número pertenece a la sucesión. Si algún dígito es 2 o 3, no pertenece.

¿Cuál es la fórmula del n-ésimo término?

M(n) = la suma, para todos los valores de i, de $b_i \cdot 4^i$, donde los $b_i$ son los dígitos binarios de n.

¿Es infinita la sucesión?

Sí. Tiene infinitos términos, aunque se vuelven más espaciados a medida que crece n.

¿En qué se diferencia del sistema binario?

El sistema binario, es decir, las sumas de potencias distintas de 2, puede representar todos los enteros no negativos. La sucesión de Moser-de Bruijn utiliza potencias de 4 en su lugar, por lo que deja fuera a la mayoría de los enteros.

Referencias

1. The OEIS Foundation. A000695: Moser-de Bruijn sequence: sums of distinct powers of 4. OEIS A000695 — términos de la sucesión, dígitos en base 4 solo 0 y 1, forma única a(k) + 2·a(l), referencias de Moser (1962) y de Bruijn (1964).
2. The OEIS Foundation. A000079: Powers of 2. OEIS A000079 — potencias de 2.
3. The OEIS Foundation. A005836: Numbers whose base-3 representation contains no 2. OEIS A005836 — sumas de potencias distintas de 3.
4. The OEIS Foundation. A003714: Fibbinary numbers. OEIS A003714 — números binarios sin dos 1 adyacentes.
5. MacTutor History of Mathematics, Universidad de St Andrews. Leo Moser (1921–1970). Biografía de Leo Moser — fechas de vida, canadiense de origen austriaco, teoría de números.
6. MacTutor History of Mathematics, Universidad de St Andrews. Nicolaas de Bruijn (1918–2012). Biografía de Nicolaas de Bruijn — fechas de vida, neerlandés, campos de trabajo.