Re: Números primos (Rússia - 2000)

["Marcelo Rufino de Oliveira" <marcelo_rufino@xxxxxxxxxxx>]

Note que os termos são dados por  a(n) = 10^n + 1,  n inteiro tal que  1 <=
n <= 2000.
Seja  n = (2^x).m  onde m é ímpar e x é um inteiro não negativo.
Assim, se m > 1:  a(n) = 10^n + 1 = 10^((2^x).m) + 1 = [10^(2^x) + 1].K,
K um inteiro qualquer, implicando que se m > 1 então a(n) nunca é primo.
Desta forma, uma condição necessária para que a(n) seja primo é que m = 1,
ou seja, que n seja um potência de 2.
Entre 1 e 2000 temos exatamente 11 potências de 2 (2^0, 2^1, 2^2, ...,
2^10).
Assim, pelo menos 2000 - 11 = 1989 números a(n) = 10^n + 1  são compostos,
que equivale a 99,45% dos termos.

Acredito que com um pouco mais de paciência dá para chegar a porcentagens
mais exatas, excluindo alguns termos da forma 10^(2^x) + 1  (0 <= x <= 10)
que são compostos, mas a solução acima já é suficiente para o que o
enunciado pede.

Até mais,
Marcelo Rufino de Oliveira


----- Original Message -----
From: <thiagobrando@connectmed.com.br>
To: <obm-l@mat.puc-rio.br>
Sent: Sunday, July 22, 2001 4:40 PM
Subject: Números primos (Rússia - 2000)


> Saudações a todos da lista!
> Acho que essa questao caiu ese ano na primeira fase da obm, de maneira
> diferente, mas com o mesmo foco... identificaçao de primos...
>
> Está na eureka no 10, olimpiadas ao redor do mundo
> (russia-2000) Seja M o conjunto que consiste nos 2000 primeiros numeros
11,
> 101 , 1001 , .... Mostre que pelo menos 99% dos elementos de M nao sao
> primos.
>
> Afinal , qual a melhor estrategia para tratar de primos?
>
> Obrigado a todos!
>
>
>
> Thiago Brando
>
>
>
>
>