Question

Descubra o próximo elemento da sequência:

0,1,1,1,12,12,12,12,12,12,100,121,122,123,123,...

KNUTH, Donald.The art of computer programming. Volume 4A: Combinatorial Algorithms, exercício 5, página 432.

Answer 1

A ideia buscada pelo autor foi a seguinte:

• Considere a sequência 0,1,4,9,16 ... (+3, +5,+7,....)
• Seja \( \rho: \mathbb{N}^+ \rightarrow \mathbb{N}^+ \) uma função que associa um natural a outro natural segundo a quantidade de algarismos que definem o natural no domínio, especificamente, se n é composto por 1 algarismos, então \( \rho(n)=1 \), se n é composto por 2 algarismos, então \( \rho(n) \)=12 ou \( \rho(n) \)=21 (lembre que 2 elementos distintos do domínio poderão ter a mesma imagem) e assim por diante, tal que o correspondente de cada algarismo é definido pela sua ordem no número (por exemplo, \( \rho(24)=12,\rho(35)=12,\) ).

Pela definição de função, temos que \( \rho (55)=22\), ou seja, cada elemento do domínio possui um único correspondente na imagem.

Em termos da sequência, teremos a seguinte função:

(a)
\[ \rho(1)=1,\rho(4)=1, \rho(9)=1,\rho(16)=12, \rho(25)=12,\rho(36)=12,\]
\[ (...), \rho(100)=122, \rho(121)=121, \rho(144)=122,(...),\rho(196)=123,\]

Logo, o próximo termo será \( \rho(225)=112\).

Comments

Adorei seu resultado, pois  o raciocínio para obtenção da resposta foi claro. No entanto, sugiro incluir p(0) = 0 e  corrigir o ρ(100) = 100, visto que 1 é significativo para a definição a quantidade de algarismos em relação ao 0.