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 pueden escribirse como una suma de potencias distintas de 4. Comienza con 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, y continúa indefinidamente. Recibe su nombre de los matemáticos Leo Moser y Nicolaas Govert de Bruijn. En la Enciclopedia en línea de sucesiones de enteros está catalogada como A000695.

Un número pertenece a la sucesión exactamente cuando su representación en base 4 utiliza solo los dígitos 0 y 1, nunca 2 ni 3. Por ejemplo, 21 en base 4 se escribe 111, por lo que pertenece a la sucesión. El número 22 en base 4 se escribe 112, por lo 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 pertenece a la sucesión.
• 90: en base 4, 90 es 1122. Contiene un 2, por lo que 90 no pertenece a 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. Introduce el número de términos que se generarán. El campo tiene el valor predeterminado 20 si se deja vacío.
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 desde 1 hasta 1000. Se rechazan los decimales, los números negativos y las entradas no numéricas. Solicitar 20 términos devuelve desde M(0) hasta M(19); el último valor mostrado es 261. Todos los cálculos se realizan en el navegador, por lo que los resultados aparecen de inmediato y no se envían datos a ningún servidor.

Sucesiones relacionadas

• Potencias de 2 (OEIS A000079): 1, 2, 4, 8, 16, 32, y así sucesivamente. 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, y así sucesivamente. Es la misma idea que la sucesión de Moser-de Bruijn, construida a partir de la base 3 en lugar de la base 4.
• Números fibbinarios (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10, y así sucesivamente. Son números cuya forma binaria no contiene dos 1 consecutivos.

Historia

Leo Moser (1921-1970) fue un matemático austrocanadiense que trabajó en teoría de números, combinatoria y geometría. Nicolaas Govert de Bruijn (1918-2012) fue un matemático neerlandés conocido por sus trabajos en combinatoria, teoría de grafos e informática; sus sucesiones de Bruijn, no relacionadas con esta, se utilizan ampliamente en teoría de la codificación. Ambos estudiaron las bases aditivas: conjuntos de enteros, como las potencias de 4, a partir de los cuales cada número representable tiene exactamente una representación como suma. La sucesión que lleva sus nombres es un ejemplo de este tipo de base.

Preguntas frecuentes

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

Aparece en la teoría aditiva de números y la combinatoria, especialmente en el estudio de los conjuntos libres de sumas y las bases aditivas. También se utiliza para enseñar conversión de bases y operaciones bit a bit en informática.

¿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 término n.º?

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.