Re: [obm-l] RE: [obm-l] RE: [obm-l] potência de 2

On 5/22/05, kleinad2@globo.com <kleinad2@globo.com> wrote:

Na minha resolução anterior, eu acabei confundindo D_x = 1 + 2 + ... + 2^x
por não ter escrito D_x = 1 + 2 + 3 + 4 + 5 + ... + 2^x, e acabei, em vez
de somando de 1 a 2^x, pegando apenas as potências de 2... Por isso o erro!

Espero ter consertado... abaixo, a resolução devidamente alterada. Agora
encontrei S_1023 = 2^19 - 3*2^11 = 518144, que é algo mais próximo da estimativa
numérica do Bruno, e me parece estar tudo certo desta vez.

Ok!

Chame de S_k a soma f(1) + ... + f(k). É fácil ver que f(2n + 1) = f(2n),
e também que f(1) = 0. Se B_k = número de múltiplos de 2^k menores ou iguais
a n, vale f(n) = B_1 + B_2 + ... (a partir de um certo x, k>=x implica B_k
= 0).

Como B_k é a parte inteira de n/2^k (denota-se [n/2^k]), isto é, o único
inteiro tal que B_k <= n/2^k < B_k + 1, temos f(n) = [n/2] + [n/2^2] + [n/2^3]
+ ... . Por essa razão, f(2n + 1) = f(2n) = n + [n/2] + [n/2^2] + ... =
n + f(n), logo S_(2^k + 1) = f(1) + ... + f(2^k + 1) = 2*(f(2) + f(4) +
f(6) + ... + f(2^k)) = 2*( 1 + f(1) + 2 + f(2) + ... + 2^(k-1) + f(2^(k-1)))
= 2*S_(2^(k-1)) + 2*D_(k-1), onde D_(x) = 1 + 2 + 3 + 4 + 5 + ... + 2^x.

Repare que vc pode escrever S_(2^(k-1)) = S_(2^(k-1) + 1) - f(2^(k-1)),
assim chegamos a S_(2^k + 1) = 2*S_(2^(k-1) + 1) + 2*(D_(k-1) - f(2^(k-1))).

Tem-se f(2^(k-1)) = [2^(k-1)/2] + [2^(k-1)/2^2] + ... = 1 + 2 + 2^2 + 2^3
+ ... + 2^(k-2) = 2^(k-1) - 1, assim temos D_(k-1) - f(2^(k-1)) = 2^(k-2)*(2^(k-1)
+ 1) - 2^(k-1) + 1.

Segue que S_(2^k + 1) = 2*S_(2^(k-1) + 1) + (2^(k-1) - 1)^2 + 2^(k-1) +
1.

A idéia então é calcular S_1023 usando S_1023 = S_1025 - 2*f(1024) = S_(2^10
+ 1) - 2*f(2^10). Aplicando repetidamente o raciocínio de há pouco, chegaremos
a

S_1025 = 2^9*S_(3) + (2^9 + 1) + 2*(2^8 + 1) + 2^2*(2^7 + 1) + ... + 2^8*(2
+ 1) + (2^9 - 1)^2 + 2*(2^8 - 1)^2 + 2^2*(2^7 - 1)^2 + ... + 2^8*(2 - 1)^2.

Após algumas manipulações e sabendo que S_3 = 1, chegamos a S_1025 = 2^19
- 2^12 - 2. Como f(1024) = 1 + 2 + 2^2 + ... + 2^9 = 2^10 - 1, vem que S_1023
= S_1025 - 2*f(1024) = 2^19 - 3*2^11 = 518144.

[],
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
=========================================================================