Re: Problema Republica Tcheca

["Bruno Leite" <bruleite@xxxxxxxxxx>]

Ui, agora que estou vendo que me esqueci de explicar de onde veio esta
fórmula z(n)=n+[n/4]+[n/8]+[n/16]+...
Obrigado por ter explicado!

Mas foi assim mesmo que eu pensei, usando a mesma idéia que Lagrange(foi ele
mesmo?) usou para calcular qual a maior potência de um primo que divide n!

Sobre o chute para 82308, eu fiz bem parecido com você, primeiro calculei
para 82304 ou 82305 e rapidamente cheguei ao meu "chute".

Bruno

-----Mensagem original-----
De: Ralph Costa Teixeira <ralph@mat.puc-rio.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Sexta-feira, 20 de Julho de 2001 17:26
Assunto: Re: Problema Republica Tcheca


>>> Seja z(n)=n+[n/4]+[n/8]+[n/16]+...
>
>    Legal sua solução, Bruno. Voce definiu g(n) como "o numero de vezes que
>2 divide n". Então o somatório de g(k) de 1 até n é o número de "2" que
>dividem todos os números de 1 até k, por assim dizer. Você pode calcular
>isso assim: olhe para os números de 1 a k e
>
>    conte 1 para cada número par
>    conte 1 extra para os múltiplos de 4
>    conte 1 mais para os múltiplos de 8
>    ...
>
>    Chegando à sua fórmula:
>
>    SUM(g(k), 1 a n) = [n/2]+[n/4]+[n/8]+...
>
>    Para f(n), adicione uma linha às regras:
>
>    conte 1 para cada ímpar
>
>    EnTão SUM(f(k), 1 a n) = [(n+1)/2]+[n/2]+[n/4]+[n/8]+[n/16]+...
>
>    que corresponde à sua fórmula para z(n) quando n é par.
>
>>> Fazendo umas continhas, vemos que z(82308)=123457
>
>    E aqui, não sei qual método você usou para achar o 82308, mas eu
pensava
>em algo assim para ajudar:
>
>    z(n) <= n + n/4 + n/8 + n/16 + ... = n + n/2 = 3n/2
>
>    Então n >= 2z(n)/3.
>
>    Se z(n)=123457, então n>=2.123457/3 = 82304,???. Assim, n=82305 é um
>ótimo lugar para começar a busca...
>
>    Abraço,
>        Ralph
>
>
>