[obm-l] =?ISO-8859-15?Q?RE=3A=20=5Bobm=2Dl=5D=20pot=EAncia=20=20de=20=202?=

[kleinad2@xxxxxxxxx]

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: obm-l@mat.puc-rio.br
 '>'From: Pacini bores <pacini.bores@globo.com>
 '>'Subject: [obm-l] potência  de  2
 '>'Reply-To: obm-l@mat.puc-rio.br
 '>'
 '>'
 '>'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
=========================================================================