[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] 3 problemas



Última ressalva, agora em (***) .... x_2(n) == teto(n/2) = quantidade de
números ímpares menores ou iguais a n (mod 2), e não conforme eu escrevi...
Abaixo, corrigido.

As duas últimas tabelas estavam com alguns erros de conta... Abaixo, espero
ter consertado todos (setas <==== indicam onde estava errado)

Bruno Bruno (brunobbruno@gmail.com) escreveu:
>
>Estou com dificuldades com esses daqui:
>
>1) Qual o algarismo das unidades do número x = 1^1 + 2^2 + 3^3 +.... +
>n^n ?

Seja x(n) = 1^1 + 2^2 + 3^3 + ... + n^n.

De maneira geral, se p e q são primos distintos, x == a (mod p) e x == b
(mod q), temos
x = k*p + a
x = m*q + b
logo
q*x = k*p*q + a*q
p*x = m*p*q + b*p
o que somando dá
(p + q)*x == a*q + b*p (mod p*q)

Mas p + q é invertível mod p*q, portanto x == (a*q + b*p)/(p + q) (mod p*q).

Seja x_2(n) a classe de congruência de x(n) mod 2. Analogamente para x_5(n).

(***) Módulo 2, as parcelas não nulas em x_2(n) vêm dos ímpares menores ou
iguais a n, portanto x_2(n) == teto(n/2) (mod 2).

Para x_5(n), usando o teorema de Euler-Fermat (se u == v (mod 5) e u == w
(mod fi(5) = 4) então u^u == v^u == v^w (mod 5)) vem

x_5(n) == (1^1 + 2^2 + 3^3 + 4^4) + (1^2 + 2^3 + 3^4 + 4^1) + (1^3 + 2^4 +
3^1 + 4^2) + ... (mod 5)

A soma das parcelas em parênteses são claramente cíclicas em mmc(4,5) = 20,
portanto se n = 20*m + b, então x_5(n) = m*x_5(20) + x_5(b).

Felizmente não é difícil construir uma tabela de valores x_5(b), b = 1,
2, ..., 19; os valores a serem somados são assim:

1^1 2^2 3^3 4^4 0
1^2 2^3 3^4 4^1 0
1^3 2^4 3^1 4^2 0
1^4 2^1 3^2 4^3 0

Ordenadamente em b, da esquerda pra direita e de cima para baixo, estes são
os valores de b^b mod (5). Isto pode ser melhorado:

1 -1 2 1 0
1 -2 1 -1 0 <====
1 1 -2 1 0
1 2 -1 -1 0

Portanto, para obter x_5(b) "basta" ir somando, mod 5, ordenadamente até a b-
ésima casa. Em particular, x_5(20) = 4, portanto se n = 20*m + b, b = 1,
2, ..., 19, tem-se x_5(n) = 4*m + x_5(b). Os valores de x_5(b) são (b = 1,
2, ..., 20)

1 0 2 3 3 <====
4 2 3 2 2 <====
3 4 2 3 3
4 1 0 4 4

Temos 2 + 5 = 7, e o inverso de 7 mod 10 é 3. Pelas observações iniciais,

x == 3*(2*x_5(n) + 5*x_2(n)) == 6*x_5(n) + 15*x_2(n) == 6*x_5(n) + 5*x_2(n)
(mod 10).

O x_2(n) é facilmente calculável, o x_5(n) dá um pouco mais de trabalho, e
admito que a solução é feia. Seria ótimo se alguém obtivesse uma fórmula
fechada para x_5(n)..

[]s,
Daniel

=========================================================================
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
=========================================================================