1. 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 \{a(n)\}_{n\ge1} tal que cada valor k aparece exatamente a(k) vezes na sequência. Em outras palavras, a frequência de k em \{a(n)\} é igual a a(k)-vezes.
Formalmente, ela é definida pelas condições:
a(1)=1,
e, para todo n\ge1,
a(n+1)\;=\;1 \;+\;a\bigl(n+1 - a\bigl(a(n)\bigr)\bigr).
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:
  • a(1)=1.
  • a(2)=1 + a\bigl(2 - a(a(1))\bigr)=1 + a\bigl(2 - a(1)\bigr)=1 + a(1)=2.
  • a(3)=1 + a\bigl(3 - a(a(2))\bigr)=1 + a\bigl(3 - a(2)\bigr)=1 + a(3-2)=1 + a(1)=2.
  • a(4)=1 + a(4 - a(a(3)))=1 + a(4 - a(2))=1 + a(4-2)=1 + a(2)=1+2=3.
    Continuando assim, obtemos
1,\,2,\,2,\,3,\,3,\,4,\,4,\,4,\,5,\,5,\dots
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 a(1)=1. Depois, para cada k\ge1, coloque o inteiro k repetido a(k) vezes na lista. Enquanto você não ultrapassar o comprimento desejado n, continue calculando novos a(n) 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 k aparece exatamente a(k) vezes, definida por
a(1)=1, \quad a(n+1)=1+a\bigl(n+1 - a(a(n))\bigr).
Seus primeiros termos são
1,\,2,\,2,\,3,\,3,\,4,\,4,\,4,\,5,\,5,\dots

Exercícios relacionados