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

[Chicao Valadares <chicaovaladares@xxxxxxxxxxxx>]

Se é pra calcular via programaçao, existe uma formula
p/ f(n) = n - S(n) , onde S(n) é a soma dos digitos de
n na base 2(bits)....entao basta fazer um pequeno loop
de n = 1 ate 1023 e calcular o resultado...
Essa formula é uma consequencia daquela famosa formula
do calculo da potencia de um primo de n!, que alias,
tambem da pra ser usada pra se calcular essa soma, é
somente vc perceber que, por exemplo, entre 513=2^9 +
1 e 1023=2^10 - 1  , vc dividirá cada numero deste
intervalo por 2, 2^2, 2^3 ...ate 2^9 entao , sem
considerar a funçao piso aplicada a cada um, pode-se
fazer (1/2 + 1/2^2 ...1/2^9)(513 + 514...1023) e
calcular a funçao piso deste resultado...Aplica-se
esse raciociocio pra todas as potencias de 2 restantes
e soma-se todos os resultados...o resultado deverá ser
muito proximo do resultado real, coisa de unidades a
mais, já que a funçao piso nao esta sendo aplicada de
forma totalmente correta a partir da formula
original....
Quem nao souber do que eu estou falando veja em:
http://mathworld.wolfram.com/Factorial.html


--- kleinad2@globo.com escreveu:
> 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
>
=========================================================================
> 

"O Binômio de Newton é tão belo como a Vênus de Milo.
O que há é pouca gente para dar por isso... "
Fernando Pessoa - Poesias de Alvaro Campos

_________________________________________________________________
As informações existentes nessa mensagem e no(s) arquivo(s) anexado(s) 
são
para uso restrito, sendo seu sigilo protegido por lei. Caso não seja
destinatário, saiba que leitura, divulgação ou cópia são proibidas. 
Favor
apagar as informações e notificar o remetente. O uso impróprio será 
tratado
conforme as normas da empresa e a legislação em vigor. Agradecemos sua
colaboração.


The information mentioned in this message and in the archives attached 
are
of restricted use, and its privacy is protected by law. If you are not 
the
addressee, be aware that reading, disclosure or copy are forbidden. 
Please
delete this information and notify the sender. Inappropriate use will 
be
tracted according to company's rules and valid laws. Thank you for your
cooperation.


	
	
		
____________________________________________________Yahoo! Mail, cada vez melhor: agora com 1GB de espaço grátis! http://mail.yahoo.com.br
=========================================================================
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
=========================================================================