Re: [obm-l] Problema de fatoriais

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sat, Jan 10, 2004 at 02:46:27PM -0300, Carlos Maçaranduba wrote:
> Alguem se habilita a fazer a letra c da questao???A a
> e a b eu ja fiz.......
> 
> 1a)Mostre que a potencia de um primo p que exatamente
> divide n! é igual a [n/p]+ [n/p^2] +
> [n/p^3]+...[n/p^f]
> sendo p^f <= n < p^(f+1).
> ->beleza :)
> 
> b)Usando a letra a ,escreva a fatoraçao de 100!.
> ->beleza :)
> 
> c)Sendo S_b(n) indicando a soma dos digitos de n na
> base b(ex: 3 na base 2 é igual a 11. Entao S_2(3) =
> 2).
> Mostre que a potencia de 2 que divide n! é igual a 
> n - S_2(n).

n/2 - [n-2] é igual a 0 se n é par e 1/2 se n é ímpar, ou seja,
é a0/2 onde a0 é o algarismo das unidades de n na base 2.

Analogamente
n/4 - [n/4] = a1/2 + a0/4
n/8 - [n/8] = a2/2 + a1/4 + a0/8
...

onde a1, a2, ... são os algarismos de n na base 2 (da direita para a esquerda).

Assim

n - [n/2] - [n/4] - [n/8] - ... 
= (n/2 - [n/2]) + (n/4 - [n/4]) + (n/8 - [n/8]) + ...
= a0*(1/2+1/4+1/8+...) + a1*(1/2+1/4+1/8+...) + a2*(1/2+1/4+1/8+...)
= a0 + a1 + a2 + ...
= S_2(n)

> Ache a formula geral para a potencia do
> primo p que divide n! em funçao de n,p,S_b(n).
> ->não fiz :(

Este eu deixo para você. É parecido. []s, N.
=========================================================================
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
=========================================================================