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

[kleinad2@xxxxxxxxx]

Hehehe, para variar, eu não acerto nem de segunda... Vc está certo, Bruno,
S_3 = 2 (fiquei com o f(3) na cabeça...), e então basta acrescentar 2^9
ao meu resultado anterior, obtendo S_1023 = 2^19 - 3*2^11 + 2^9 = 518656,
e finalmente nossas respostas coicidem!

[]s,
Daniel
 '>'-- Mensagem Original --
 '>'Date: Mon, 23 May 2005 00:39:11 -0300
 '>'From: Bruno França dos Reis <bfreis@gmail.com>
 '>'To: obm-l@mat.puc-rio.br
 '>'Subject: Re: [obm-l] RE: [obm-l] RE: [obm-l] potência de 2
 '>'Reply-To: obm-l@mat.puc-rio.br
 '>'
 '>'
 '>'S_3 = f(1) + f(2) + f(3)
 '>'f(1) = 0
 '>'f(2): 2! = 2, ==> f(2) = 1
 '>'f(3): 3! = 3, ==> f(3) = 1
 '>'Logo S_3 = 0 + 1 + 1 = 2.
 '>'(isso pq na ultima passagem vc usa "sabendo que S_3=1")
 '>'Não vi o resto, Daniel. Será que arrumando isso chegaremos na mesma

 '>'resposta?
 '>'
 '>'Veja aí, estou morrendo de sono! Até amanhã!
 '>'
 '>'Abraço!
 '>'Bruno
 '>'
 '>'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
 '>'> =========================================================================
 '>'> 
 '>'
 '>'
 '>'
 '>'-- 
 '>'Bruno França dos Reis
 '>'email: bfreis - gmail.com <http://gmail.com>
 '>'gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
 '>'icq: 12626000
 '>'
 '>'e^(pi*i)+1=0



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