Re: [obm-l] Digitos de 1000!

["Qwert Smith" <lord_qwert@xxxxxxxxxxx>]

Acabo de ver que na verdade nao e nada dificil e nao precisa saber quantos e 
quais sao os pirmos < 1000, ja que e desnecessario fatorar o fatorial :)

Queremos (1000!/10^429) mod 10 basta escrever
1*2*3*...*11*12*13*...*988*989*990*998*999*1000 ( mod 10 ) ->
1^100*2^100*3^100*4^100*5^100*6^100*7^100*8^100*9^100*0^100 ( mod 10 )
que isso da 0 ja sabiamos mas como queremos o ultimo  digito nao nulo vamos 
descartar 2,5 e 0
sobra entao:
1^100*3^100*4^100*6^100*7^100*8^100*9^100 =
1^99*1*2^99*2*3^99*3*...*8^100*9^99*9
mas como 9^99 = -1^99,  7^99 = -3^99, etc da pra ver que os termos se anulam 
com excecao do 8 , logo sobra 1*3*4*6*7*9*8^100, e nem precisa de muito 
braco pra chegar em 2 (mod 10)

para o caso geral n!
seja n = x ( mod 10)
e a = [n/10] ( maior inteiro menor ou igual )
temos n! ( mod 10 ) = 1^a*2^a*3^a*4^a*5^a*6^a*7^a*8^a*9^a*0^a*(x!)
como queremos o ultimo algarismo nao nulo denovo jogamos fora 2,5,0 e 
resovemos da mesma maneira que acima.   Veja que se  x >=5, devemos 
descartar o 2 e 5 de x! tb.

-Auggy



>From: "Qwert Smith" <lord_qwert@hotmail.com>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: [obm-l] Digitos de 1000!
>Date: Mon, 22 Mar 2004 18:21:31 -0500
>
>O problema e que 1000 e um pouquinho maior que 50... sao 168 primos < 1000, 
>por isso to tentando ver se tem uma outra saida
>
>-Auggy
>
>btw... para n=50 e simples e direto ver que 50!=
>30414093201713378043612608166064768844377641568960512000000000000
>
>com 12 zeros e ultimo algarismo nao nulo tb 2
>
>
>>From: Johann Peter Gustav Lejeune Dirichlet 
>><peterdirichlet2002@yahoo.com.br>
>>Reply-To: obm-l@mat.puc-rio.br
>>To: obm-l@mat.puc-rio.br
>>Subject: Re: [obm-l] Digitos de 1000!
>>Date: Mon, 22 Mar 2004 19:40:00 -0300 (ART)
>>
>>Ainda me lembro de como eu achei para n=50.Sao 10 zeros no final 
>>(acho).Alias essa foi um questao da OPM....Temos que eliminar as fontes de 
>>zeros.Foiu o que fiz ai...
>>
>>
>>1*1*3*4*1*6*7*8*9*1
>>11*6*13*14*3*16*17*18*19*2
>>21*11*23*12*1*26*27*28*29*3
>>31*16*33*34*7*36*37*38*39*4
>>41*21*43*22*9*46*47*48*49*1
>>
>>Os 1,11,21,31,41 nao importam. Agora e meio porrada mas da para andar 
>>bem....Depois eu tento escrever decentemente, mas levem isso como alguma 
>>ajuda...
>>
>>So uma coisa: tenha um pouco mais de consideraçao pela sua lingua natal...
>>
>>Fabiano Sant'Ana <fabiano.ufo@terra.com.br> wrote:
>>não tenho a minima idéia de como resolver isso sem usar "BrutalForce"(ou 
>>seja, calcular os números 1 a 1)...
>>
>>[]s
>>Fabiano
>>----- Original Message -----
>>From: Cláudio (Prática)
>>To: obm-l@mat.puc-rio.br
>>Sent: Monday, March 22, 2004 12:08 PM
>>Subject: [obm-l] Digitos de 1000!
>>
>>
>>Oi, pessoal:
>>
>>Já que o assunto é potências de primos que dividem n!, aqui vai um 
>>bonitinho:
>>
>>1) (clássico) Por quantos zeros termina a representação decimal de 1000!
>>
>>2) (menos conhecido e mais difícil) Qual o último algarismo não nulo na 
>>representação decimal de 1000!
>>
>>3) (generalização) Qual o último algarismo não nulo de n!?  Dica não muito 
>>útil: é sempre par se n > 1.
>>
>>
>>[]s,
>>Claudio.
>>
>>
>>
>>---
>>Outgoing mail is certified Virus Free.
>>Checked by AVG anti-virus system (http://www.grisoft.com/).
>>Version: 6.0.624 / Virus Database: 401 - Release Date: 15/03/04
>>
>>
>>
>>
>>TRANSIRE SVVM PECTVS MVNDOQVE POTIRI
>>
>>CONGREGATI EX TOTO ORBE MATHEMATICI OB SCRIPTA INSIGNIA TRIBVERE
>>
>>Fields Medal(John Charles Fields)
>>
>>
>>
>>
>>
>>---------------------------------
>>Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!
>
>_________________________________________________________________
>Check out MSN PC Safety & Security to help ensure your PC is protected and 
>safe. http://specials.msn.com/msn/security.asp
>
>=========================================================================
>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
>=========================================================================

_________________________________________________________________
Is your PC infected? Get a FREE online computer virus scan from McAfee® 
Security. http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963

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