Oi, 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 + ... + 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^(k-2) = D_(k-2) = D_(k-1) - 2^(k-1), assim temos S_(2^k + 1) = 2*S_(2^(k-1) + 1) + 2^k. 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 = S_(2^10 + 1) = 2^9*S(2 + 1) + 9*2^10 = 2^9 + 9*2^10. Como f(1024) = f(2^10) = D_9 = 2^10 - 1, temos S_1023 = S_1025 - 2*f(1024) = 2^9 + 9*2^10 - 2*2^10 + 2 = 2^9 + 14*2^9 + 2 = 15*2^9 + 2. Espero n�o ter errado nada... []s, Daniel '>'-- Mensagem Original -- '>'Date: Sun, 22 May 2005 11:05:30 -0300 '>'To: [email protected] '>'From: Pacini bores <[EMAIL PROTECTED]> '>'Subject: [obm-l] pot�ncia de 2 '>'Reply-To: [email protected] '>' '>' '>'Ol� Pessoal , '>' '>'Algu�m poderia me ajudar no problema abaixo ? '>' '>'Sabendo que f(n) � maior pot�ncia de 2 que divide n! , '>'determine o valor de '>' '>'f(1) + f(2) +...+ f(1023) . '>' '>'Agrade�o qualquer ajuda . '>'[]?s Pacini '>' '>' '>' '>'========================================================================= '>'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 '>'========================================================================= ========================================================================= 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 =========================================================================
