Problema da sequência

["Bruno Fernandes C. Leite" <superbr@xxxxxxx>]

>De: Marcelo Souza <marcelo_souza7@hotmail.com>
>Para: <obm-l@mat.puc-rio.br>
>Enviada em: Quarta-feira, 18 de Outubro de 2000 20:45
>Assunto: 2problemas
>
>
>Oi pessoal da lista!
>Alguém poderia resolver pra mim os dois problemas que se seguem.
>1. Sendo S_1 a sequencia 1,2,3,4,5,6,..., S_2 a sequencia 2,3,4,5,6,7,...e
>S_3 a sequencia 3,3,5,5,7,7,.... Generalizando S_n+1é obtida tomando S_n e
>adicionando 1 para cada inteiro que é divisível por n. Ache todos os n
>inteiros tal que os primeiros n-1 inteiros de S_n são n.

Olha, eu acho que encontrei uma solução não tão comprida. Aí vai ela(ou um
esboço dela):

Notação: p(n) é o n-ésimo primo.
A é a matriz infinita que se obtém escrevendo a sequência S_1 na primeira
linha, S_2 na segunda, etc:
1  2  3  4  5  6  7  8  9    10  11  12  13...
2  3  4  5  6  7  8  9  10  11  12  13  14...
3  3  5  5  7  7  9  9  11  11  13  13  15...
etc

Vou mostrar que se p(n)<=i<p(n+1), o i-ésimo termo de S_p(n+1) é p(n+1).
A prova é por indução em n. Para n pequeno, ok. Agora suponha que a
hipótese é verdadeira até n. Vamos mostrar que ela vale para n+1.

Temos que se p(n)<=i<p(n+1), o i-ésimo termo de S_p(n+1) é p(n+1).
Mas então, se p(n)<=i<p(n+1) e k>p(n+1), o i-ésimo termo de S_k é k pois k
é sempre múltiplo de k.
Logo, se p(n)<=i<p(n+1), o i-ésimo termo de S_p(n+2) é p(n+2).

Como S_f é uma sequência não decrescente para qualquer f natural, se
i>=p(n+1), o i-esimo termo de S_p(n+2) é >=p(n+2).
Em particular, se p(n+1)<=i<p(n+2), o i-esimo termo de S_p(n+2) é >= p(n+2).

Considere a coluna p(n+2)-1 de A.. Na primeira linha ela vale p(n+2)-1, na
linha seguinte ela passará a valer p(n+2) e é claro que a partir daí ela
não muda mais, até a linha p(n+2). Na linha p(n+2) ela vale p(n+2). Então
se i<p(n+2), temos que o i-ésimo termo de S_p(n+2) é <= p(n+2). Logo
p(n+1)<=i<p(n+2) implica que o i-ésimo termo de S_p(n+2)=p(n+2),
completando a indução.

------------------------------------------

(1)p é primo <=> S_p tem p-1 p`s no início.
 Isso porque na linha p(da matriz infinita) a primeira coluna vale p e a
(p-1)-ésima coluna vale p. Como as linhas e colunas da matriz são
não-decrescentes, todas as colunas entre 1 e p-1 também valem p.

(2)Se c é um numero composto, então existe n tal que p(n)<=c<p(n+1).
Na linha p(n), a coluna p(n) vale p(n+1), que é >c. Logo, na linha c, a
coluna p(n) NÃO pode valer c pois o seu valor é ao menos p(n+1)>c

Conclusão: os primeiros n-1 inteiros de S_n são iguais a n se e somente se
n é primo.

--------
Está certo tudo isso, ou tem besteira aí no meio?

Bruno Leite