- O que é Sequência de Golomb? Explique sua construção.
Passo 1
O enunciado pede para definirmos o que é a Sequência de Golomb e explicarmos como ela é construída. Esse conteúdo faz parte do estudo de sequências recursivas e descrições autodescritivas em Discreta/Teoria de Números.
Passo 2
A Sequência de Golomb é uma sequência de inteiros positivos
tal que cada valor
aparece exatamente
vezes na sequência. Em outras palavras, a frequência de
em
é igual a
-vezes.
Formalmente, ela é definida pelas condições:
Formalmente, ela é definida pelas condições:
e, para todo
,
Essa fórmula recursiva garante que, ao “ler” os termos já construídos, o próximo valor se ajusta para manter a propriedade de autodescrição.
Passo 3
Vamos gerar os primeiros termos para ilustrar a construção:
-
. -
. -
. -
.
Continuando assim, obtemos
e de fato “1” aparece uma vez, “2” aparece duas vezes, “3” aparece três vezes, etc.
Passo 4
Outra forma intuitiva de ver a construção é a seguinte: comece com
. Depois, para cada
, coloque o inteiro
repetido
vezes na lista. Enquanto você não ultrapassar o comprimento desejado
, continue calculando novos
pela recursão. Essa auto-referência faz da Golomb uma sequência não-linear e autodescritiva.
Resposta
A Sequência de Golomb é a sequência de inteiros positivos em que cada número
aparece exatamente
vezes, definida por
Seus primeiros termos são