Re: [obm-l] Oi Pessoal

["Domingos Jr." <dopikas@xxxxxxxxxx>]

algumas idéias...

(http://mathworld.wolfram.com/EulersTotientTheorem.html)

phi(10^1000) é o número de inteiros de 1...10^1000 que são relativamente
primos com 10^1000.
temos que todos os múltiplos de 2 ou 5 são os únicos inteiros com divisor em
comum com 10^1000, logo, o número de múltiplos de 2 e 5 é (10^1000)/2 +
(10^1000)/5 - (10^1000)/10 = 3/5(10^1000)

phi(10^1000) = 2/5(10^1000) = 2^1001.5^999
se mdc(10^1000, a) = 1, temos
a^phi(10^1000) = 1 (mod 10^1000) pelo teorema de Euler

suponha que para algum n, a(n) = a(n+1) (mod 10^1000)
a(n+2) = a^a(n+1) = a^(10^1000.q + a(n)) = (a^(10^1000))^q . a^a(n) =
(a^(10^1000))^q . a(n+1)

se q = 2k, temos
a(n+2) = (a^(10^1000))^2k . a^a(n) = a^a(n) = a^a(n+1)

se q = 2k + 1,
a(n+2) = (a^(10^1000))^(2k + 1) . a(n+1) = (a^(10^1000))^2k . a^(10^1000) .
a(n+1) = a^(10^1000) . a(n+1)

a(n+2) = a^(10^1000) . a(n+1)
a(n+2)² = [a^(10^1000) . a(n+1)]² = a(n+1)²
a(n+2)² = a(n+1)²

aqui entram os detalhes técnicos, é simples ver que os primos da fatoração
a(m) são os mesmos da fatoração de a, sendo assim, se mdc(a, 10^1000) = 1,
mdc(a(m), 10^1000) = 1 para todo m >= 1.

se considerarmos o grupo multiplicativo formato pelos elementos de 1 até
10^1000 relativamente primos a 10^1000, temos:
a(n+2)² = a(n+1)² <=> (a(n+2) - a(n+1)).(a(n+2) + a(n+1)) <=> a(n+2) =
a(n+1) ou a(n+2) = -a(n+1)

se conseguirmos eliminar o caso a(n+2) = -a(n+1), ou eliminarmos a
possibilidade de que q seja ímpar, bastaria provar que, dado a, mdc(a,
10^1000) = 1, se existe algum n tal que a(n) = a(n+1), temos que após n
todos os 10.000 últimos dígitos da seqüência estarão fixados.

sobram os casos em que 2|a ou (exclusivo) 5|a, se 10|a, a resposta é
trivial, já que só de olhar para 10^10^10 dá pra ver que essas séries vão
ter números com muitos zeros no final e esse número de zeros atinge 1000 bem
rapidamente...

[ ]'s


>     Oi pessoal,
>  Tenho acompanhado a lista pelo site da obm à alguns
> dias e então resolvi entrar. Tenho um problema legal
> (gostaria da ajuda de um dos brilhantes participantes
> da lista, como: Johann Peter Gustav Lejeune
> Dirichlet...): Seja a(1) = a; a(n+1) = a^a(n); Prove
> que: para qualquer a > 1 inteiro, os últimos 1000
> dígitos da expansão decimal de a(n) ficam
> eventualmente constantes !!!
>   Okakamo Kokobongo
>
> _______________________________________________________________________
> Busca Yahoo!
> O serviço de busca mais completo da Internet. O que você pensar o Yahoo!
encontra.
> http://br.busca.yahoo.com/
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> O administrador desta lista é <nicolau@mat.puc-rio.br>
> =========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================