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