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

[Bruno França dos Reis <bfreis@xxxxxxxxx>]

Ronaldo, fiz aqui uma versaozinha em C otimizada, usando a função
phi(n) que diz o expoente de 2 na fatoração em primos de n, e a função
f(n), que é a função do problema (fiz f(n) = phi(1) + phi(2) + ... +
phi(n)), e tb soma(n) = f(1) + f(2) + f(3) + ... + f(n). Dá pra
otimizar bem mais isso aí, mas já é bem rápido pra calcular soma(1023),
então não vi necessidade.

Abraço,
bruno


int phi(int n) {
  if(n%2 == 1) return 0;
  return (phi(n/2) + 1);
}

int f(int n) {
  int i, s = 0;
  for (i = 1; i <= n; i++)
    s += phi(i);
  return soma;
}

int soma(int n) {
  int i, s = 0;
  for (i = 1; i <= n; i++)
    s += f(i);
  return s;
}

int main() {
  int n = 1;
  while(n) {
    printf("digite n (0 para sair): ");
    scanf("%d",&n);
    printf("soma(n)=%d\n\n", soma(n));
  }
}

On 5/22/05, Ronaldo Luiz Alonso <ronaldo.luiz.alonso@bol.com.br > wrote:

>Sabendo  que  f(n)  é  maior potência  de  2  que  divide  n! ,
>determine  o valor  de
>f(1) + f(2) +...+ f(1023) .

Vejamos mais de perto:

1! = 1  a maior potência de 2 que divide 1! é 0 (2^0 = 1).
2! = 2  a maior potência de 2 que divide 2! é 1 (2^1 = 2).
3! = 6=3.2.1  a maior potência de 2 que divide 3! é 1 (2^1 = 2).
4! = 24 = 4.3.2.1  a maior potência de 2 que divide 4! é 3 (2^3 = 8).
...
Pelos exemplos acima parece que não há uma regra geral.

Note que com 5! por exemplo, a maior potência de 2 que divide 5!
continua sendo 3 (porque 5 é primo).

          Mas no caso de 6 (que não é primo)
a maior potência de 2 que divide 6! será 4.

                Peço desculpas  a quem não sabe C, mas eu faria um programa
de computador para calcular a soma (pois o computador atrofiou meu cérebro)
e desafio alguém a pensar em algo mais "força bruta" e feio que isso:

/*  calcula a soma   f(1) + f(2) + ...+ f(x) */
unsigned int soma_pot2_fatorial( unsigned int x)
{     int i;
    soma =0
    for (i = 1; i <= x; i++)
    {
         int k = fatorial (i); /* calcula o fatorial de i -- note que k é
uma variável de escopo local */
         while (( k % 2) == 0){  /* enquanto o resto da divisão por 2 for
zero */
            soma = soma++; /* incrementa soma */
             k = k/2; /* k recebe a parte inteira da divisão de k por 2 */
         }// fim enquanto
     }// volta ao laço com o valor de i incrementado.
     return soma;
}

Acho que não isso não ajuda, mas
pelo menos calcula a soma pedida ...

[]s  Ronaldo L. Alonso

=========================================================================
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
gpg-key: http://planeta.terra.com.br/informatica/brunoreis/brunoreis.key
icq: 12626000

e^(pi*i)+1=0