Universidade Federal de Santa Maria

Ci. e Nat., Santa Maria, v. 44, e58, 2022

DOI: 10.5902/2179460X70592

ISSN 2179-460X

Submissão: 04/06/2022 • Aprovação: 17/08/2022 • Publicação: 19/12/2022

1 INTRODUÇÃO

2 CONCEITOS E RESULTADOS PRELIMINARES

3 RESULTADO PRINCIPAL

4 NÚMERO DE ALGARISMOS NA IMAGEM DA FUNÇÃO

5 DEMONSTRAÇÃO DO TEOREMA 19

6 CONCLUSÕES

REFERÊNCIAS

Matemática

A finitude dos pontos periódicos da sequência de Conway ordenada

The finitude of the periodic points of the Conway ordered sequence

Eudes Antonio Costa I

Fernando Soares de Carvalho I

Élis Gardel da Costa Mesquita I

I Universidade Federal do Tocantins, Arraias, TO, Brasil

Resumo

Neste artigo, apresentamos algumas propriedades da sequência de Conway ordenada. Tais propriedades estão relacionadas com órbitas e pontos fixos. Nosso principal resultado é determinar uma limitação para a quantidade de algarismos na órbita de qualquer número natural x, ou seja, começando com qualquer termo inicial finito, os termos da sequências terão comprimento limitado a, no máximo, 21 algarismos e, portanto, as órbitas são relativamente periódicas.

Palavras-chave: Função; Sequência; Órbita; Ponto fixo

Abstract

In this paper, we present some properties of the Conway ordered sequence or counting sequence. Such properties are related to orbits and fixed points. Our main result is to determine a limitation for the number of digits in the orbit of any natural number x, that is, starting with any finite initial term, the sequence terms will have a length limited to a maximum of 21 digits, and therefore the orbits are relatively periodics.

Keywords: Fixed point; Function; Sequence; Orbit

1 INTRODUÇÃO

Uma sequência conhecida e denominada sequência de Conway ou também sequência de olhar e dizer, foi apresentada por John Conway em Conway (1987), cuja regra de formação é dada por:

Para gerar um elemento da sequência a partir do elemento anterior, leia os dígitos do elemento anterior (da esquerda para a direita), contando o número de dígitos em grupos do mesmo dígito.

Veja um exemplo:

1,11,21,1211,111221,312211,13112221,1113213211

(1)

É importante destacar que, embora a sequência apresentada em (1) seja iniciada apenas com o dígito (algarismo) 1, a sequência de Conway pode ser iniciada por qualquer algarismo. Por exemplo, começando com qualquer d ∈ {0,2,3,4,5,6,7,8,9}, ou seja d ̸= 1, tem-se

d,1d,111d,311d,13211d,111312211d,31131122211d,1321132132211d,...

Neste trabalho, o foco principal é analisar algumas propriedades de uma sequência, uma variação da sequência de Conway, que será chamada de sequência de Conway ordenada. Nesta variação da sequência, a lei de formação de cada elemento a partir do primeiro é dada por:

Para gerar um elemento da sequência a partir do elemento anterior, leia os dígitos do elemento anterior em ordem crescente, contando e registrando o número de dígitos em grupos do mesmo dígito.

Agora começando com o dígito 1, tem-se:

1,11,21,1112,3112,211213,312213,212223,114213

(2)

Aqui também é importante destacar que a sequência apresentada em (2) poderá iniciar com qualquer número natural, por exemplo

9282575788, 2225273819, 114213171819, 5112131415171819,...

A sequência de Conway ordenada, dada na Equação (2), com termo (dígito) inicial 1 está listada como a sequência A005151 na Enciclopédia Online de Sequências Inteiras (Sloane et al., 2003, A005151). Outras variações da sequência de Conway, e suas relações com a mesma, são apresentadas nos trabalhos de Brier et al. (2020b), Brier et al. (2020a) e Martín (2006).

Vale ressaltar que Bronstein e Fraenkel (1994) mostraram que qualquer sequência de Conway ordenada com termo inicial finito têm comprimento limitado de seus termos após algumas iterações, e de forma independente, também em Costa e Santos (2019). Neste trabalho, vamos melhorar este resultado, obtendo uma limitação para o comprimento dos termos da sequência após um número finito de iterações. Na seção 2 são apresentadas definições e resultados iniciais para o desenvolvimento do trabalho, tais como, definição da aplicação que gera a sequência de Conway ordenada e resultados relacionados à órbita de um ponto (elemento, termo ou número) inicial e também pontos fixos desta sequência. Na seção 3 apresentamos o nosso principal resultado, o Teorema 19; na seção 4 são apresentados resultados com o intuito de estabelecer a cota superior para a quantidade de algarismos nos termos da sequência após algumas iterações; e por fim, a seção 5 é dedicada a demonstração do resultado principal.

2 CONCEITOS E RESULTADOS PRELIMINARES

Em todo o texto, Nn denota o subconjunto de números naturais menores ou iguais a n, isto é, Nn = {0,1,2,3,..,n − 1,n}, para todo n natural. E ainda, para n ≥ 1, o conjunto Fn denota o conjunto de todos os números naturais com exatamente n algarismos.

Vamos utilizar a notação #x = n para expressar a quantidade de algarismos do número natural x ∈ Fn.

Com o intuito de analisar a sequência de Conway ordenada, vamos utilizar a aplicação (função) de modo que a sequência

x1, x2 = (x1), x3 = (x2), x4 = (x3),..., xn = (xn−1),

Seja gerada pelo processo iterativo da sequência de Conway ordenada. Formalmente temos a seguinte definição:

Definição 1. Dado um número natural qualquer com n algarismos, ou seja, x Fn, representado por x = x1x2x3 ···xn, sejam 0 ≤ xn1 < xn2 < ... < xnk ≤ 9 os algarismos distintos que aparecem em x, e pj > 0, j = 1,...,k, a quantidade de vezes que o algarismo xnj N9 aparece na representação do número x. Definimos,

(x) = P1xn1P2xn2 ...Pkxnk.

Exemplo 2. Dado o número x = 11645578885022, veja que xn1 = 0, xn2 = 1, xn3 = 2, xn4 = 4, xn5 = 5, xn6 = 6, xn7 = 8 e xn8 = 7 são os algarismos distintos; temos também que p0 = 1, p1 = 1, p2 = 2, p4 = 1, p5 = 3, p6 = 1, p7 = 1 e p8 = 3; assim, a soma p1 + p2 + ... + p8 = 14 é a quantidade de algarismos de x, ou seja, #x = 14. Tem-se (x) = 1021221435161738 e #(x) = 16.

Segue da Definição 1 que a função (que tem como domínio o conjunto dos números naturais ou inteiros positivos) é claramente não sobrejetora, por exemplo, não existe x, tal que (x) = 1. Nem é injetiva, pois para x = 2020 e y = 2200 temos que (x) = (y) = 2022.

O comportamento da sequência de Conway ordenada pode ser analisada por sucessivas iterações da aplicação . Sendo assim, os conceitos de órbita, sequência periódica e ponto fixo serão essenciais, detalhes adicionais podem ser consultados em Devaney (2018).

Definição 3 . (a) Seja a aplicação de Conway ordenada. Para todo número x natural as iterações de são definidas por,

ϕ0(x) = x, ϕ1(x) = ϕ(x), ϕk(x) = ϕ(ϕk−1(x)), k ≥ 2.

(b) A órbita de um número x, é o conjunto

O(x) = {x, ϕ(x), ϕ2(x), . . . , ϕk(x), . . . } .

Exemplo 4. A órbita de x = 1, é dada por, (1) = 11, 2(1) = 21, 3(1) = 1112, 4(1) = 3112, 5(1) = 211213, 6(1) = 312213, 7(1) = 212223, 8(1) = 114213, 9(1) = 31121314, 10(1) = 41122314, 11(1) = 31221324, 12(1) = 21322314, 13(1) = 21322314, . . . , ou seja,

Neste caso, observe que, n(1) = n−1(1), para todo n > 12.

Definição 5. Diremos que a órbita de x é:

(a) periódica, ou que x é ponto periódico de ordem m, se para algum inteiro m tivermos m(x) = x, i(x) = x e m+i(x) = i(x), para todo i < m.

(b) relativamente (eventualmente) periódica de ordem m se a órbita de x não é periódica, mas existe um natural k tal que a órbita de k(x) é periódica de ordem m.

Observação 6. Note que se x pertencer a uma órbita de período m, então todos os pontos da órbita de x também tem período m.

Exemplo 7. Veja que números naturais x = 10714213141516172819 e u = 10812213241516271819 tem a incrível propriedade que (x) = u e (u) = x, ou seja, a órbita de x, ou a órbita de u, é periódica de ordem 2 (ou x pertence a um 2-ciclo).

No Exemplo 4, veja que a órbita de x = 1 é relativamente periódica de ordem 1, pois para k ≥ 12 temos que k(x) = 12(x). Já para y = 22 tem-se que (22) = 22 é periódica de ordem 1.

Definição 8. Diremos que um número x no domínio de é um ponto fixo, se (x) = x, ou seja, uma órbita periódica de ordem 1 é composta por um ponto fixo da função .

Note que se x é um ponto relativamente periódico de ordem 1, para algum k > 0, então k+1(x) é um ponto fixo. De fato, pois teremos k+1(x) = k(x), ou ainda, (k+1(x)) = (k(x)) =k+1(x), ou seja, k+1(x) é um ponto fixo. Veja o exemplo 9 a seguir.

Exemplo 9. Dado o número , a órbita de x é dada por:

Observe que neste caso, a órbita do número x é relativamente periódica de ordem 1 e possui oito elementos distintos. Logo, 8(x) = 1031223314 é um ponto fixo com 10 algarismos.

Exemplo 10. Seja x = 1234567890, temos

Veja que para qualquer k ≥ 4, k(x) = 101112213141516171819, ou seja, 101112213141516171819 é um ponto fixo com 21 algarismos.

Exemplo 11. Veja que no Exemplo 7, o número x = 10714213141516172819 é periódico de ordem 2, assim considerando a função µ = 4, segue que µ(10714213141516172819) = 10714213141516172819 .

Observação 12. Note que, se o número x tem período m para a função , então x,(x),...,m−1(x) são todos pontos fixo da função ψ = m. De fato, para k = 0,1,...,m − 1, seja y = k(x), assim

ψ(y) = ψ(k(x)) = m(k(x)) = k(m(x)) = k(x) = y .

E mais, se x tem período m para a aplicação , então x é ponto fixo de qualquer função ψ = mk, para k natural.

Salientamos que o único ponto fixo com dois algarismos é x = 22. De acordo com o que foi apresentado em Costa e Santos (2019), não temos pontos fixos com 1, 3, 4, 5, 6, 7 ou 9 algarismos. Considerando números com 8 algarismos tem-se pontos fixos, por exemplo, (10311233) = 10311233 e (10213223) = 10213223. É possível ainda, listar algumas classes de pontos fixos com 8 e 10 algarismos, como pode ser visto no Exemplo 13 a seguir.

Exemplo 13. (a) Se a e b são números inteiros com 3 < a < b, temos os pontos fixos com 8 algarismos: 31331a1b, 3112331a, 2132231a, 3112331a e 1031331a.

(b) Se a é um número inteiro com 3 < a, temos os pontos fixos com 10 algarismos: 103122331a.

Proposição 14. Sejam k ≥ 2 e x = p1xi1p2xi2 ...pkxik um ponto fixo de , tal que, pj = 2̸ e xij ̸= 2 para todo j ∈ {1,...,k}. Considere y = p1xi1p2xi2 ...pkxik22 então (y) é um ponto fixo de , com k +2 algarismos.

Demonstração. Devemos mostrar que (y) = y. Sabemos que pij ̸= 2 e xij ̸= 2 para todo j ∈ {i1,...,ik}, assim temos dois casos a considerar:

Primeiro caso: xi1 < 2 < xi2 ocorre quando xi1 ∈ {0,1} e 2 < xi2, assim (y) = pi1xi122pi2xi2 ...pikxik.

Segundo caso: xi1 < xi2 < 2 ocorre quando xi1 = 0 e xi2 = 1 , assim (y) = pi1xi1pi2xi222pi3xi3 ...pikxik. Portanto, em ambos os casos tem-se ((y)) = (y).

É claro que podemos obter pontos fixos com diferentes quantidades de algarismos, como suscitado no Exemplo 15.

Exemplo 15. Em complemento ao Exemplo 13. Para 3 < a < b os números da forma x = 31331a1b são pontos fixos de com 8 algarismos e não aparece nenhum algarismo 2, considerando y = 31331a1b22 tem-se que (y) = 3122331a1b é um ponto fixo com 10 algarismos. Já o número 1011113141516171819 é um ponto fixo com 19 algarismos, e não aparece o algarismo 2, assim para y = 101111314151617181922, tem-se que (y) = 101112213141516171819 é um ponto fixo de 21 algarismos.

Uma importante particularidade manifesta para os casos em que no número x não aparece o algarismo zero. Para esses números a imagem da função não se altera se permutarmos a posição dos algarismos. Por exemplo, (23432) = 222314 = (22334). Isso ocorre porque os números 23432 e 22334 são formados apenas por uma permutação dos algarismos que o compõe.

Definição 16. Dado um número x = x1x2 ...xn com n algarismos, considere o número x′ com n algarismos da forma , obtido de x permutando (trocando a posição de) seus algarismos, isto é, x′j (1 ≤ j ≤ n) é igual a algum xi (1 ≤ i ≤ n), com cada xj ∈ N9.

Por exemplo os números 139, 193, 319, 391, 913 e 931 são obtidos por meio de permutações dos algarismos do número 319. Aqui x′ indicará qualquer número inteiro obtido de x permutando seus algarismos. Por simplicidade diremos que x′ é um número permutado obtido de x. Aqui consideraremos também o caso em que o 0 (zero) aparece como algarismo do número x com n > 1 algarismos, ainda assim teremos (consideramos) os números permutados x′ com n algarismos. Por exemplo, 012 e 021 são números permutados com 3 algarismos obtidos de 102.

O próximo resultado é de fácil verificação.

Proposição 17. Costa e Santos (2019) Sejam x e x′ números com n algarismos no domínio da função , então (x) = (x′).

Observação 18. Os pontos periódicos apresentados neste trabalho foram encontrados a partir de um código utilizando o software Octave, em que cada algarismo que compõe o número x é gerado de forma aleatória e o código roda até que o critério de parada (k(x) = x) é alcançado para algum k ≥ 1 inteiro.

3 RESULTADO PRINCIPAL

Em Bronstein e Fraenkel (1994) mostra-se, que começando com qualquer termo inicial x (número natural) finito, todas as sequências (iterações) têm comprimento de seus termos limitado, ou seja, a órbita de x é relativamente periódica. No recente trabalho Costa e Santos (2019) mostraram que se x é um ponto fixo da forma x = x1x2x3 ···xn, então n ≤ 100, ou seja, o número de algarismos de um ponto fixo não é superior a 100 e que os pontos relativamente periódicos teriam no máximo 33 algarismos. Observamos que esta estimativa pode ser melhorada, nosso principal resultado é mostrar que:

Teorema 19. Para todo número x no domínio da função , a órbita de n(x) converge para um ponto (relativamente) periódico com no máximo 21 algarismos.

A demonstração será apresentada na Seção 5. Todo ponto relativamente periódico e os elementos que formam o período tem no máximo 21 algarismos. Em outras palavras, todo ponto x do domínio da é periódico ou relativamente periódico, ou seja, a órbita de x estabiliza em um ponto periódico com ordem finita m com no máximo 21 algarismos, isto é, existe um natural t0 ≥ 1 tal que t0(x) ∈ F∗21, em que F∗n denota o conjunto de todos os números naturais com no máximo n algarismos, com n ≥ 1. Como consequência direta do Teorema 19, temos o seguinte resultado.

Teorema 20. Não existe ponto fixo de com mais de 21 algarismos.

Demonstração. Suponha que x seja um ponto fixo com mais de 21 algarismos. De acordo com Teorema 19, existe um t inteiro positivo, tal que . Mas, se x é ponto fixo então para qualquer t temos t(x) = x, ou seja, t(x) teria mais de 21 algarismos, contrariando o fato de para algum t0. Portanto, concluímos que qualquer x ponto fixo de tem no máximo 21 algarismos.

4 NÚMERO DE ALGARISMOS NA IMAGEM DA FUNÇÃO

É possível perceber que há uma dificuldade computacional para encontrar pontos (relativamente) periódicos para a função . De fato, basta observar que dado um número x com n algarismos, tem-se N = 9 · 10n−1 números a serem verificados, tornando o trabalho computacional árduo, à medida que o valor de n cresce. Os resultados apresentados nesta seção, têm o intuito de limitar o valor de n, possibilitando a otimização do trabalho computacional.

Proposição 21. Seja um número com pa ≥ 1 algarismos repetidos, com a ∈ N9 e 10k−1 ≤ pa < 10k, então #(x) = k +1 para qualquer k ≥ 1 inteiro.

Demonstração. Para quaisquer k ≥ 1 e pa ≥ 1 inteiros, como 10k−1 ≤ pa < 10k, a quantidade de algarismos de pa é igual a k, ou seja, #pa = k. Sendo , segue que (x) = paa. Como # (x) = (#pa)+1, conclui-se que # (x) = k +1.

Proposição 22. Costa e Santos (2019) Dado um número x com n algarismos, temos que

p1 + p2+ ··· + pk = n ,

sendo pi, i = 1,2,...,k, a quantidade de vezes que o algarismo xij aparece em x.

Demonstração. É uma consequência imediata da Definição 1, tendo em vista que o número x possui n algarismos na representação decimal e que pi1 é a quantidade de vezes que o algarismo xi1 aparece, pi2 é a quantidade de vezes que o algarismo xi2 aparece, e assim sucessivamente. Donde obtemos o resultado.

Combinando os dois resultados anteriores, temos

Proposição 23. Dado um número x com n algarismos, tal que p1 + p2 + ··· + pk = n, sendo pi a quantidade de vezes que o algarismo xij aparece em x, então

Demonstração. Sejam x1,x2,...,xk ∈ N9 os 1 ≤ k ≤ 10 algarismos distintos do número x. Podemos permutar os algarismos de x, caso seja necessário, de tal forma que

, com x1 < x2 < ··· < xk .

Para cada bloco de xj algarismos repetidos faça Segue da Proposição 21, que o número de algarismos de (yj)

é #pi +1, com 10k−1 ≤ pi < 10k, para algum natural k ≥ 1. Veja que o número de algarismos de (x′) é obtido pela adição do número de algarismos de (yj), ou seja,

#(x′) = #(y1)+#(y2)+ ... +#(yk)

Por fim, segue da Proposição 17 que o número de algarismos de (x′) é igual ao número de algarismos de(x), donde concluímos o resultado desejado.

Segue diretamente Proposição 23 que

Corolário 24. Costa e Santos (2019) Dado um número x com n algarismos.

(a) Se todos os algarismos de x são distintos e n ≤ 10, então (x) possui 2n algarismos.

(b) Admita que x tenha em sua representação decimal k < n algarismos distintos, com 1 ≤ k ≤ 10, então (x) possui no mínimo 2k algarismos.

Uma questão que nos interessa: dado um número x com n > 1 algarismos, existe uma cota superior para o número de algarismos da função na primeira iteração? Existe uma cota superior para o número de algarismos da função após a segunda iteração? Estamos interessados em determinar se a órbita de x estabiliza, isto é, se após um número finito de iterações, a órbita de x converge para algum ponto (relativamente) periódico.

Exemplo 25. Sejam , , números com 10 algarismos. A órbita de x é

a órbita de y é

e a órbita de z é

Observando estas órbitas particulares, verifica-se que (x) possui 3 algarismos, (y) possui 10, enquanto que (z) possui 20 algarismos; já 2(x) possui 4 algarismos, 2(y) possui 10 e 2(z) possui 21 algarismos.

Os dois próximos exemplos, e as tabelas, compara a quantidade de algarismos de (x), sendo x um número composto por 30 algarismos e a distribuição dos algarismos é distinta.

Exemplo 26. Seja x um número formado por 30 algarismos, com x1,x2,...,xk {0,1,...,9}, sendo 1 ≤ k ≤ 10 os k algarismos distintos do número x. A Tabela 1 exibe a quantidade de algarismos de (x), em que a distribuição dos algarismos em x busca ser “equânime”.

Tabela 1 - Número de algarismos

k	#xi	(x)	#((x))
1	30	30x1	3
2	15-15	15x115x2	6
3	10-10-10	10x110x210x3	9
4	9-9-9-3	9x19x29x31x4	8
5	6-6-6-6-6	6x16x26x36x46x5	10
6	5-5-5-5-5-5	5x15x25x35x45x55x6	12
7	4-4-4-4-4-4-6	4x14x24x34x44x54x64x7	14
8	4-4-4-4-3-3-3-3	4x14x24x34x43x53x63x73x8	16
9	3-3-3-3-3-3-4-4-4	3x13x23x33x43x54x64x74x84x9	18
10	3-3-3-3-3-3-3-3-3-3	3x13x23x33x43x53x63x73x83x93x10	20

Fonte: Elaborado pelos autores (2022)

Exemplo 27. Seja x um número formado por 30 algarismos, com x1, x2, . . . , xk {0,1, . . . , 9}, sendo 1 ≤ k ≤ 10 os k algarismos distintos do número x. A Tabela 2 exibe a quantidade de algarismos de (x), em que a distribuição dos algarismos em x não é equânime.

Tabela 2 - Número de algarismos 2

k	#xi	(x)	#((x))
1	30	30x1	3
2	15-15	15x115x2	6
3	10-10-10	10x110x210x3	9
4	10-10-9-1	10x110x29x31x4	10
5	10-10-8-1-1	10x110x28x31x41x5	12
6	10-10-7-1-1-1	10x110x27x31x41x51x6	14
7	10-10-6-1-1-1-1	10x110x26x31x41x51x61x7	16
8	10-10-5-1-1-1-1-1	10x110x26x31x41x51x61x71x8	18
9	10-10-4-1-1-1-1-1-1	10x110x26x31x41x51x61x71x81x9	20
10	10-10-3-1-1-1-1-1-1-1	10x110x26x31x41x51x61x71x81x91x10	22

Fonte: Elaborado pelos autores (2022)

O próximo resultado procura caracterizar a situação descrita nos Exemplos 25 e 27.

Proposição 28. Dados os número x e y com n algarismos, tal que x tenha k1 algarismos distintos e y tenha k2 algarismos distintos, com 1 ≤ k1 < k2 ≤ 10 e x1 = y1,x2 = y2,...,xk1 = yk1,xk1+1 = yk1+1,...yk2. Se pi = qi para i = 1,2,...,k1 − 1 então o número de algarismos de (x) é menor que o número de algarismos de (y), sendo pi a quantidade de vezes que o algarismo xi aparece em x; e qi a quantidade de vezes que o algarismo yi aparece em y.

Demonstração. Sejam x1,x2,...,xk1 ∈ {0,1,...,9} os 1 ≤ k1 < 10 algarismos distintos do número x e y1,y2,...,yk2 ∈ {0,1,...,9} os 1 < k2 ≤ 10 algarismos distintos do número y. Como k2 > k1 reordene os algarismos de y, de forma que

y1 = x1,...,yk1 = xk1 .

Pela Proposição 22, temos que

p1 + p2+ ··· + pk1 = n , e

q1+ q2 + ··· + qk2 = n .

Veja que

(x) = pi1x1pi2x2 ...pik1xk1 , e

(y) = pi1 x1pi2 x2 . . . pik1−1 xk1−1qik1 xk1 qik1+1 yk1+1 . . . qik2 yk2 , assim #(y) > #(x), visto que qik1 + qik1+1 + . . . + qik2 = pik1 .

Segue da Proposição 28, como no Exemplo 27, que quanto maior a quantidade de algarismos distintos em x, um número com n algarismos, maior será a quantidade de algarismos em (x), visto que a quantidade de algarismos de cada pi é menor ou igual que a quantidade de algarismos de n. Dessa forma, para estabelecer uma cota superior para #(x), basta considerar o caso em que (x) apresenta a maior quantidade possível de algarismos distintos, ou seja, pi ≥ 1 para todo i = 1,2,...,k. Isto significa que todos os elementos pertencentes a N9 devem estar presentes em x e os algarismos em x não podem ser distribuídos de forma não equânime, como no Exemplo 25.

Para todo n ≥ 10, o Algoritmo 1 estabelecerá como cada algarismo dever ser distribuído e repetido, de modo que este procedimento estabeleça uma distribuição que garanta que #(x) seja o maior valor possível.

Algoritmo 1. Dado um número natural x com n algarismos, como 10k−1 ≤ n < 10k para algum k natural, tem-se:

n = ak−1ak−2 ...a1a0 = ak−110k−1+ ak−210k−2+ ··· + a1101+ a0 , ak−1 = 0 .

• Primeiro passo: Colocar (distribuir) cada algarismo xj ∈ N9 exatamente 10k−2 vezes;
• Segundo passo: Se a quantidade de algarismos restantes for menor ou igual a 9 · 10k−2, escolha qualquer algarismo pertencente a N9 e repita (distribua) este algarismo até finalizar a quantidade de algarismos; e finaliza o processo.
• Terceiro passo: Se após o primeiro passo, a quantidade de algarismos restante for maior que 9 · 10k−2, escolha algarismos distintos pertencentes a N9 e distribua a cada um deles exatamente 9 · 10k−2, até que o segundo passo possa ser realizado.

Os exemplos seguintes mostrarão a funcionalidade do Algoritmo 1 para gerar um número x com n ≥ 10 algarismos, tal que (x) tenha o maior número possível de algarismos. Apresentamos, pelos exemplos, alguns casos particulares, com o intuito de explorar um pouco mais o Algoritmo 1, pensando em um leitor menos familiarizado. Para um leitor mais experiente é possível suprimir a leitura destes, evitando que se tornem repetitivas e enfadonhas as argumentações e procedimentos.

Exemplo 29. Vamos exibir um número x com 21 algarismos, ou seja, temos n = 2·10+1. No primeiro passo devemos distribuir cada algarismo 1 vez, ou seja,

p1 = 1, p2 = 1, p3 = 1, p4 = 1, p5 = 1, p6 = 1, p7 = 1, p8 = 1, p9 = 1, p0 = 1 .

E temos um número com 10 algarismos distintos. Escolhemos os algarismos 1 e acrescentamos mais 9 vezes o algarismo. E finalizamos com o algarismo 2 aparecendo 3 vezes, assim teremos:

p1 = 10, p2 = 3, p3 = 1, p4 = 1, p5 = 1, p6 = 1, p7 = 1, p8 = 1, p9 = 1, p0 = 1 .

Assim (x) = 101013213141516171819 também tem 21 algarismos.

Exemplo 30. Vamos exibir um número x com 39 algarismos, ou seja, temos n = 3·10+9. No primeiro passo devemos distribuir cada algarismo 1 vez, ou seja,

p1 = 1, p2 = 1, p3 = 1, p4 = 1, p5 = 1, p6 = 1, p7 = 1, p8 = 1, p9 = 1, p0 = 1 .

E temos um número com 10 algarismos distintos. Escolhemos os algarismos 0, 1 e 2 e acrescentamos mais 9 vezes o algarismo. E finalizamos com o algarismo 3 aparecendo 3 vezes, assim teremos:

p1 = 10, p2 = 10, p3 = 3, p4 = 1, p5 = 1, p6 = 1, p7 = 1, p8 = 1, p9 = 1, p0 = 10 .

Assim, (x) = 10010110233141516171819 tem 23 algarismos.

Exemplo 31. Vamos exibir um número x com 99 algarismos, ou seja, temos n = 9·10+9. No primeiro passo devemos distribuir cada algarismo 1 vez, ou seja,

p1 = 1, p2 = 1, p3 = 1, p4 = 1, p5 = 1, p6 = 1, p7 = 1, p8 = 1, p9 = 1, p0 = 1 .

Escolhemos os algarismos de 0 a 8 e acrescentamos mais 9 e o algarismo 9 mais 8, assim teremos:

p1 = 10, p2 = 10, p3 = 10, p4 = 10, p5 = 10, p6 = 10, p7 = 10, p8 = 10, p9 = 9, p0 = 10 .

Assim (x) = 10010110210310410510610710899 tem 29 algarismos.

Exemplo 32. Vamos exibir um número x com 995 algarismos, ou seja, temos n = 9·102+9·10+5. No primeiro passo devemos repetir (distribuir) cada algarismo 10 vezes, ou seja,

p1 = 10, p2 = 10, p3 = 10, p4 = 10, p5 = 10, p6 = 10, p7 = 10, p8 = 10, p9 = 10, p0 = 10 .

Agora nos algarismos de 1 à 9 vamos acrescentar mais 90 algarismos, e obtemos

p1 = 100, p2 = 100, p3 = 100, p4 = 100, p5 = 100, p6 = 100, p7 = 100, p8 = 100, p9 = 100, p0 = 10 .

E já temos um número com 990 algarismos. Escolhemos o algarismo 0 acrescentamos mais a0 = 85, assim teremos:

p1 = 100, p2 = 100, p3 = 100, p4 = 100, p5 = 100, p6 = 100, p7 = 100, p8 = 100, p9 = 100, p0 = 95 .

Assim, (x) = 950100110021003100410051006100710081009 tem 39 algarismos.

Exemplo 33. Vamos exibir um número x com 2023 algarismos, ou seja, temos n = 2 · 103+0 · 102+2 · 10+3. No primeiro passo devemos repetir (distribuir) cada algarismo 102 vezes, ou seja,

p1 = 100, p2 = 100, p3 = 100, p4 = 100, p5 = 100, p6 = 100, p7 = 100, p8 = 100, p9 = 100, p0 = 100 .

Agora, acrescentar ao algarismo 9 mais 900 vezes e ao algarismo 8 mais 223, ou seja,

p1 = 100, p2 = 100, p3 = 100, p4 = 100, p5 = 100, p6 = 100, p7 = 100, p8 = 223, p9 = 1000, p0 = 100 .

Assim (x) = 10001001100210031004100510061007223810009 tem 41 algarismos.

Proposição 34. Seja x um número com n ≥ 10 algarismos. Se x é dado respeitando o Algoritmo 1, então a quantidade de algarismos de (x) será máxima.

Demonstração. Como no Algoritmo 1, suponha 10k−1 ≤ n < 10k e portanto n possui k − 1 algarismos. Pela Proposição 28 para que (x) tenha o maior número de algarismos, no número x deverá aparecer os 10 algarismos, ou seja, devemos ter pi ̸= 0, para i = 0,1,2,...,9, sendo cada pi o marcador para a contagem de dígitos do número x. Observa-se que quanto maior o número de algarismos de cada pi, maior será o número de algarismos de (x). Segue do Algoritmo1 que,

pi = 10k−2+ δ, com 10k−3 < δ ≤ 9 · 10k−2 .

(3)

Dessa forma, todos os valores de pi foram maximizados (otimizados).

A Proposição 35 a seguir, irá estabelecer uma cota superior para o número de algarismos da função após a primeira iteração.

Proposição 35. Seja x um número natural com n ≥ 10 algarismos, então a quantidade de algarismos de (x) é menor ou igual a 10(k +1), sendo k = #n.

Demonstração. Como o número de algarismos de x é n ≥ 10, segue da Proposição 28 que (x) será maior se todos os algarismos em N9 figuram pelo menos 10k−2 vezes. Como 10k−1 ≤ n < 10k, teremos cada pi máximo se δ = 9 · 10k−2, assim para todo i na Equação (3), considere

p′i = 10k−2+9 · 10k−2 = 10k−1 ,

ou seja, o número de algarismos de cada , isto é # . Sabemos que

(x) = p00p11p22p33p44p55p66p77p88p99 . Segue da Proposição 23 que o número de algarismos de (x) é

Portanto #(x) é limitado por 10(k +1).

Observação 36. Na Proposição 35, veja que ao aplicar a função , a quantidade de algarismos de (x) diminuirá enquanto k ≥ 2, sendo k a quantidade de algarismos da quantidade de algarismos do número x.

5 DEMONSTRAÇÃO DO TEOREMA 19

Antes de demonstrar o Teorema 19, mostraremos um resultado auxiliar, o Lema 37 seguinte, que garante que o número de algarismos da quantidade da quantidade de algarismos da iteração de aplicado ao número x será no máximo 21 dígitos, para todo 10 ≤ n < 100, em que #x = n.

Lema 37. Seja x qualquer número natural com 10 ≤ n < 102 algarismos, então a quantidade de algarismos de 3(x) é menor que 21.

Demonstração. Temos que a quantidade de algarismos de x é 10 ≤ n < 102, ou seja, n = a1 · 10 + a0. Segue do Algoritmo 1 que (x) será maior se todos os algarismos em N9 figuram pelo menos uma vez. Veja que cada pi = 1 + δ com 0 ≤ δ ≤ 9, assim para todo i temos pi ≤ 10, nem todos podem ser 10, ao menos um p1 ≤ 9. Digamos p0 = p1 = p2 = p3 = p4 = p5 = p6 = p7 = p8 = 10 e p9 = 9. Segue da Proposição 23 que o número de algarismos de (x) é

isto é, #(x) é limitado por 29 = 2 · 10 + 9. Neste caso, novamente pelo Algoritmo 1 temos que 2(x) será maior se todos os algarismos em N9 figuram pelo menos uma vez. Temos ainda a quantia de 19 para distribuir e no máximo 2 algarismos podem chegar a 10. Digamos p0 = p1 = 10, p2 = 2 e p3 = p4 = p5 = p6 = p7 = p8 = p9 = 1. Mais uma vez usando a Proposição 23, obtemos que o número de algarismos de 2(x) é

ou seja, #2(x) é limitado por 22 = 2 · 10+2. Disto obtemos do Algoritmo 1 que 3(x) será maior se todos os algarismos em N9 figuram pelo menos uma vez. Temos ainda a quantia de 12 para distribuir, e no máximo 1 algarismo podem chegar a 10. Digamos p1 = 10, p0 = p2 = p3 = 2 e p4 = p5 = p6 = p7 = p8 = 1 = p9 = 1. Logo, da Proposição 23 temos que quantidade de algarismos de 3(x) é

Portanto #3(x) é limitado por 21 algarismos. Consequentemente, no máximo, na terceira iteração de x teremos uma limitação de 21 dígitos para todo 10 ≤ n < 100.

Na Tabela 3 exibimos a quantidade máxima de algarismos na iteração de , para um número x com 10 ≤ n < 100 algarismos.

Tabela 3 - Número máximo de algarismos na iteração

	#x	máx. #	máx. #2
1	10-19	21	21
2	20-29	22	21
3	30-39	23	21
4	40-49	24	21
5	50-59	25	21
6	60-69	26	21
7	70-79	27	21
8	80-89	28	22
9	90-99	29	22

Fonte: Elaborado pelos autores (2022)

Vamos representar a classe de todos os números inteiros positivos formados por no máximo 21 algarismos por M21.

Demonstração. do Teorema 19

Seja x um número natural com n ≥ 10 algarismos. Segue da Proposição 28 que o número máximo de algarismos em (x) ocorre quando os 10 algarismos de N9 figuram. Sabemos que 10k−1 ≤ n < 10k, sendo k = #n. Pela Observação 36, o número de algarismos de (x) é menor ou igual a 10(k +1). E mais, ao aplicar a função , o número de algarismos diminuirá enquanto k ≥ 2, ou seja, existe um inteiro t0 ≥ 1 tal que t0(x) M30, ou seja, a quantidade de algarismos de t0(x) será menor ou igual a 30. Assim, se k = 2 segue do Lema 37 que #3(x) será no máximo 21 algarismos. Em qualquer caso, temos que após um número finito de iterações os termos na órbita de qualquer x terão menos que 21 algarismos, ou seja, existe um inteiro t1 ≥ 1 tal que t(x) tem menos de 21 algarismos para todo t ≥ t1, ou seja, t(x) M21. Portanto, pelo princípio da casa dos pombos, para qualquer número x inicial teremos que x é um ponto relativamente periódico.

6 CONCLUSÕES

As sucessões são um assunto (conteúdo) clássico da matemática escolar. Problemas com sucessões, sejam as sequências numéricas, sequências recorrentes, progressões aritméticas ou geométricas, podem ser exploradas e apresentadas aos estudantes do ensino fundamental ou médio, veja por exemplo os trabalhos Gairín et al. (2017); Manero García et al. (2021), o banco de questões da OBMEP:BRASIL (2017), além do trabalho Costa e Santos (2019).

Neste trabalho mostramos que dado qualquer número inicial x, mesmo o caso em que (x) possui o maior número de algarismos possível, teremos que a órbita, ou a sequência de iterações é infinita, no entanto após um número finito de iterações o comprimento ou a quantidades de algarismos de n(x) será limitado superiormente por 21 algarismos. Utilizando o Princípio da Casa dos Pombos, concluímos que a sequência de Conway ordenada é sempre relativamente periódica.

Um problema ainda em aberto é determinar o número mínimo necessário de iterações para qualquer número natural x, tal que (x)t M21.

REFERÊNCIAS

BRIER, É.; G.-S. R.; NACCACHE, D.; PACCO, A.; TROIANI, E. The look-and-say the biggest sequence eventually cycles. arXiv:200607246[math.D.S, math.CO], Cornell University, 2020a.

BRIER, É.; G-S. R.; NACCACHE, D.; PACCO, A.; TROIANI, E. Stuttering conway sequences are still conway sequences. arXiv preprint arXiv:200606837[math.D.S, math.CO], Cornell University, 2020b.

BRONSTEIN, V.; FRAENKEL, A. S. On a curious property of counting sequences. The American Mathematical Monthly, [s.l.], v. 101, n. 6, p. 560–563, 1994.

CONWAY, J. H. The weird and wonderful chemistry of audioactive decay. Em In: COVER, T. M.; GOPINATH, B. (ed.). Open problems in communication and computation. Springer, New York, 173–188, 1987.

COSTA, E. A.; SANTOS, R. A. Contando algarismos. Revista da Olimpíada - IME - UFG,, Goiânia, [s.l.], n. 14, p. 61–74, 2019.

DEVANEY, R. L. An introduction to chaotic dynamical systems. 2. ed. CRC press: Boca Raton, 2018. 360 p.

GAIRÍIN, J. M.; OLLER, A. M.; MANERO, V.; MUÑOZ, J. M. (2017). La sucesión look and say. In: VIII Congreso Iberoamericano de Educación Matemática, 2017. Anais [...]. Zaragoza: Universidad de Zaragoza, 2018. p. 16–24.

MANERO GARCÍA, et al . Diseño e implementación de tareas de alta demanda cognitiva basadas en la sucesión look and say. Avances de investigación en educación matemática, [s.l.], n. 20, p. 161-183, 2021.

MARTÍN, Ó. Look-and-say biochemistry: Exponential rna and multistranded dna. The American Mathematical Monthly, [s.l.], v. 113, n. 4, p. 289–307, 2006.

OBMEP:BRASIL. Banco de Questões 2017. OBMEP - Olimpíada Brasileira de Matemática das Escolas Públicas, Sociedade Brasileira de Matemática. [S.l]: IMPA, 2017. Disponível em: www.obmep.org.br. Acesso em: 31/05/2022

SLOANE, N. J., et al. The on-line encyclopedia of integer sequences. 2003. Disponível em: http://oeis.org/A005151. Acesso em:31/05/2022

Contribuição de autoria

1– Eudes Antonio Costa

Professor Adjunto; Doutor em Matemática

https://orcid.org/0000-0001-6684-9961 • @fscarvalho@uft.edu.br

Contribuição: Writing - original draft

2– Fernando Soares de Carvalo

Professor Adjunto, Doutor em Ciências Mecânicas

https://orcid.org/0000-0001-6639-0716 • fscarvalho@uft.edu.br

Contribuição: Writing - original draft

3 – Élis Gardel da Costa Mesquita

Professor Adjunto; Doutor em Matemática

https://orcid.org/0000-0001-2385-4108 • elisgardel@uft.edu.br

Contribuição: Writing - original draft

Como citar esse artigo

COSTA, A.C.; CARVALHO, F. S.; MESQUITA, E. G. C. A finitude dos pontos periódicos da sequência de Conway ordenada. Ciência e Natura, Santa Maria, v. 44, e58, 2022. DOI: https://doi.org/10.5902/2179460X70592.