Re: Problema Republica Tcheca

["Ralph Costa Teixeira" <ralph@xxxxxxxxxxxxxx>]

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