[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] divisor

 
De: owner-obm-l@mat.puc-rio.br
Para: obm-l@mat.puc-rio.br
Cópia:
Data: Tue, 21 Jun 2005 11:54:13 -0300
Assunto: Re: [obm-l] divisor
> On Mon, Jun 20, 2005 at 10:55:04PM -0300, fgb1 wrote:
> > Pessoal, preciso de ajuda nessa:
> >
> > Um fator de 2^33 - 2^19 - 2^17 -1, entre 1000 e 5000 é:
> > a) 1993
> > b) 1992
> > c) 1983
> > d) 1982
> > e) 1972
>
N = 2^33 - 2^19 - 2^17 - 1 eh obviamente impar, o que elimina as alternativas b, d, e.
Olhando mod 3, e levando em conta que 2^par == 1 e 2^impar == 2, teremos que N == 2 - 2 - 2 - 1 == 0 ==> N soh pode ser 1983, pois 1993 nao eh divisivel por 3.
 
Mas, de fato, eu trapaceei, pois olhei antes a solucao do Nicolau e vi que 3 divide N. No entanto, usar congruencia mod 3 num problema com potencias de 2 nao eh nenhuma solucao magica. Muito pior eh a demonstracao da irracionalidade de Pi, que comeca com:
"Seja o polinomio p(x) = x^n*(1 - x)^n/n! ... "
 
[]s,
Claudio.
 
 
> 2^33 - 2^19 - 2^17 -1 = 8589279231 = 3^3 * 13 * 661 * 37021.
>
> Com isto é fácil verificar que o único divisor entre 1000 e 5000
> é 1983 = 3*661.
>
> Esta questão é perfeitamente viável no braço mesmo sem calculadora.
> Calcular que 2^33 - 2^19 - 2^17 -1 = 8589279231 deve tomar perto
> de 1 minuto se você souber que 2^16 = 65536 (faça 2^17 = 2*2^16,
> 2^19 = 4*2^17, 2^33 = 2^16*2^17) e as 5 divisões com resto
> também não demoram tanto assim.
>
> Talvez exista uma solução esperta mas eu não estou vendo.
>
> []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
> =========================================================================
>