Gerador de Sequência de Moser-de Bruijn | Calculadora de Potências de 4

O que é a sequência de Moser-de Bruijn?

A sequência de Moser-de Bruijn é uma lista de números inteiros que podem ser escritos como uma soma de potências distintas de 4. Ela começa com 0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84 e 85, e continua indefinidamente. Ela recebeu esse nome em homenagem aos matemáticos Leo Moser e Nicolaas Govert de Bruijn. Na Online Encyclopedia of Integer Sequences, é catalogada como A000695.

Um número pertence à sequência exatamente quando sua representação na base 4 usa apenas os algarismos 0 e 1, nunca 2 ou 3. Por exemplo, 21 na base 4 é escrito como 111, portanto pertence à sequência. O número 22 na base 4 é escrito como 112, portanto não pertence.

Fórmula da sequência de Moser-de Bruijn

A sequência pode ser definida de três maneiras equivalentes.

Soma de potências distintas de 4

Um número n está na sequência se puder ser escrito como

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

para algum conjunto S de inteiros não negativos, em que cada potência de 4 é usada no máximo uma vez.

Teste dos algarismos na base 4

Escreva o número na base 4. Se todos os algarismos forem 0 ou 1, o número estará na sequência. Se algum algarismo for 2 ou 3, não estará.

Substituição de binário para a base 4

Contando os termos a partir de n = 0, o termo no índice n é

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

em que os $b_i$ são os algarismos binários de n. Em outras palavras: escreva n em binário e depois leia cada algarismo binário como um algarismo na base 4, na mesma posição. Esse é o método usado pelo gerador, pois ele só precisa verificar bits e somar números.

Como calcular o n-ésimo termo

Para encontrar M(n), o gerador faz o seguinte para cada índice n, começando em n = 0:

1. Observe a forma binária de n.
2. Para cada bit igual a 1, na posição j, adicione 4^j a um total acumulado.
3. Ignore os bits iguais a 0.
4. O total acumulado é M(n).

Exemplo resolvido: M(5)

• 5 em binário é 101.
• O bit 0 (mais à direita) é 1, então adicione 4⁰ = 1.
• O bit 1 é 0, então não adicione nada.
• O bit 2 é 1, então adicione 4² = 16.
• Total: 1 + 16 = 17.

Portanto, M(5) = 17. Esse é o sexto valor produzido pelo gerador, pois a contagem começa em M(0).

Exemplo: os primeiros 32 termos

Como verificar se um número pertence à sequência

Converta o número para a base 4 e leia seus algarismos.

• 85: na base 4, 85 é 1111 (64 + 16 + 4 + 1). Aparecem apenas 0s e 1s, portanto 85 pertence à sequência.
• 90: na base 4, 90 é 1122. Ele contém um 2, portanto 90 não pertence à sequência.

Taxa de crescimento

A sequência cresce rapidamente, porque cada bit adicional no índice pode aproximadamente quadruplicar o valor que ele acrescenta. M(19) é 261. M(99) é 5.125. M(999), o maior termo que este gerador pode produzir, é 349.205. Os termos ficam cada vez mais distantes à medida que o índice cresce, o que torna a sequência esparsa: a maioria dos números inteiros nunca aparece nela, embora ela tenha infinitos termos.

Como usar o gerador da sequência de Moser-de Bruijn

1. Informe a quantidade de termos a gerar. O campo assume o valor padrão 20 quando fica em branco.
2. A lista de termos é atualizada automaticamente, começando em M(0).
3. Copie a lista completa com o botão Copy Result.

A ferramenta aceita números inteiros de 1 a 1000. Números decimais, negativos e entradas não numéricas são rejeitados. Solicitar 20 termos retorna M(0) até M(19); o último valor exibido é 261. Todos os cálculos são realizados no navegador, portanto os resultados aparecem imediatamente e nenhum dado é enviado a um servidor.

Sequências relacionadas

• Potências de 2 (OEIS A000079): 1, 2, 4, 8, 16, 32 e assim por diante. Esses são os blocos básicos dos números binários comuns.
• Somas de potências distintas de 3 (OEIS A005836): 0, 1, 3, 4, 9, 10, 12, 13 e assim por diante. A mesma ideia da sequência de Moser-de Bruijn, construída a partir da base 3 em vez da base 4.
• Números fibbinários (OEIS A003714): 0, 1, 2, 4, 5, 8, 9, 10 e assim por diante. Números cuja forma binária não contém dois 1s consecutivos.

História

Leo Moser (1921-1970) foi um matemático austro-canadense que trabalhou com teoria dos números, combinatória e geometria. Nicolaas Govert de Bruijn (1918-2012) foi um matemático neerlandês conhecido por seu trabalho em combinatória, teoria dos grafos e ciência da computação; suas sequências de de Bruijn, não relacionadas a esta, são amplamente usadas na teoria da codificação. Ambos estudaram bases aditivas: conjuntos de inteiros, como as potências de 4, a partir dos quais cada número representável tem exatamente uma representação como soma. A sequência que leva seus nomes é um exemplo desse tipo de base.

Dúvidas frequentes

Para que serve a sequência de Moser-de Bruijn?

Ela aparece na teoria aditiva dos números e na combinatória, especialmente no estudo de conjuntos livres de somas e bases aditivas. Também é usada para ensinar conversão de bases e operações bit a bit em ciência da computação.

Como gerar a sequência de Moser-de Bruijn?

Escreva o índice n em binário e depois leia cada algarismo binário como um algarismo na base 4, na mesma posição. Para n = 5 (binário 101), isso resulta em 4² + 4⁰ = 17.

Como verificar se um número pertence à sequência?

Converta-o para a base 4. Se todos os algarismos forem 0 ou 1, o número estará na sequência. Se algum algarismo for 2 ou 3, não estará.

Qual é a fórmula do n-ésimo termo?

M(n) = a soma, para todos os i, de $b_i \cdot 4^i$, em que os $b_i$ são os algarismos binários de n.

A sequência é infinita?

Sim. Ela tem infinitos termos, embora eles fiquem mais espaçados à medida que n cresce.

Em que ela difere do sistema binário?

O sistema binário, isto é, somas de potências distintas de 2, pode representar todo número inteiro não negativo. A sequência de Moser-de Bruijn usa potências de 4, portanto a maioria dos números inteiros fica de fora.