Author |
Topic: Last nonzero digit of n! (Read 1733 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Last nonzero digit of n!
« on: Nov 3rd, 2003, 9:32am » |
 Quote  Modify
|
Determine the last nonzero digit of 1,000,000,000! (without using a computer).
|
|
 IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Last nonzero digit of n!
« Reply #1 on: Nov 3rd, 2003, 12:03pm » |
Quote Modify
|
~We note that the last digit only depends upon the last digits of its factors after we toss out pairs of 2 and 5 and every instance of 0. We then have the last digit of:
(9*8*7*6*4*3)^100,000,000
We notice that with every pair of 9's we end in a 1 so 9^50,000,000*9^50,000,000 ends in 1 so:
(8*7*6*4*3)^100,000,000
7 and 3 repeat every fourth power so:
(8*6*4)^100,000,000
breaking them down into their factors and removing the 3's as we have shown gives:
2^600,000,000
every set of 5 twos leads to another 2, thus it breaks down to:
2^4
which gives 16, for a final answer of 6.~
|
|
IP Logged |
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: Last nonzero digit of n!
« Reply #2 on: Nov 3rd, 2003, 2:08pm » |
Quote Modify
|
on Nov 3rd, 2003, 12:03pm, aero_guy wrote:| We note that the last digit only depends upon the last digits of its factors after we toss out pairs of 2 and 5 and every instance of 0. |
|
I don't think this step works out in general. That factor of 180 will make a difference in the answer. The same goes for the pair of 12 and 15.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Last nonzero digit of n!
« Reply #3 on: Nov 4th, 2003, 4:43am » |
Quote Modify
|
That's what I got:
[smiley=blacksquare.gif]
4, followed by 249999998 zeros.
[smiley=blacksquare.gif]
The derivation is pretty simple, but... it uses a rather unknown proposition which I don't know how to prove. So, I am not sure it's fair...
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Last nonzero digit of n!
« Reply #4 on: Nov 4th, 2003, 10:00am » |
Quote Modify
|
Would that be the Stirling formula? It struck me that for an argument this large, the Stirling approximation should have more than sufficient accuracy to determine the last non-zero digit (the variance being contained well down in the digits we know should be zero anyway). But I didn't take the time to try it out.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Last nonzero digit of n!
« Reply #5 on: Nov 4th, 2003, 7:15pm » |
Quote Modify
|
I think it is highly unlikely that Stirling's Formula could give all the significant digits of N! for very large N. There is a shortcut to compute the number of zeros at the end, and if Stirling's could give the rest of the digits, this would be a way to exacty compute N! without multiplying all the integers <=N together.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Last nonzero digit of n!
« Reply #6 on: Nov 5th, 2003, 12:42am » |
Quote Modify
|
If F(n) = last nonzero digit of n!, then I come up with: for 0[le]r<5,
F(5d+r) = r! 2d F(d) (mod 5)
Knowing F mod 5 is sufficient, because we also know it must be even.
Barukh, how did you do it?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Last nonzero digit of n!
« Reply #7 on: Nov 5th, 2003, 2:20am » |
Quote Modify
|
Bravo, Eigenray!! You’ve got the idea!
on Nov 5th, 2003, 12:42am, Eigenray wrote:| Barukh, how did you do it? |
|
Let E(n, p) be the maximal power of p that divides n! (e.g. E(8, 2) = 7). Let pm…p0 be the representation of n in radix p. Then the following holds (Source: Graham et al, "Concrete mathematics", ex. 4.40):
n! / pE(n, p) = (-1) E(n, p) pm! … p0! (mod p).
E(n,p) is computed as [sum]k>0 [smiley=lfloor.gif] n / pk [smiley=rfloor.gif]. Put p=5 to get the required digit.
I wish to know whether a more elegant derivation exists...
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Last nonzero digit of n!
« Reply #8 on: Nov 5th, 2003, 3:44am » |
Quote Modify
|
I originally saw this listed somewhere as a computing exercise, but it seemed doable by hand. Here's how I got that recurrance:
Let E(n) = number of times 5 divides n! = number of times 10 divides n!. Then we're looking for n!/10E modulo 10, so it's sufficient to find G(n):= n!/5E mod 5. Let n=5d+r, and consider:
G(n) = n!/5E(n)
= (1...4)[5](6...9)[10].....[5d](1...r)/5E(n)
= 4!d 5d d! r!/5E(n) = (-1)d r! d!/5E(d)
= (-1)d r! G(d)
This recurrence is equivalent to the result Barukh quotes above, since r runs through the base-5 digits of n, from right to left, and the d's all sum to E(n). Using Wilson's theorem, this extends to all primes.
Since we're really looking for F(n) = n!/10E = G(n)/2E, replace (-1) with (-1) 2-1=2 to get a formula for F.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Last nonzero digit of n!
« Reply #9 on: Nov 6th, 2003, 2:17am » |
Quote Modify
|
Really elegant derivation, Eigenray! Especially, I liked the relation: E(n) = E(d) + d. 
on Nov 5th, 2003, 3:44am, Eigenray wrote:| Using Wilson's theorem, this extends to all primes. |
|
As they don't specify otherwise, the formula I've mentioned in the previous post holds for every p (not only prime)?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Last nonzero digit of n!
« Reply #10 on: Nov 7th, 2003, 2:42am » |
Quote Modify
|
on Nov 6th, 2003, 2:17am, Barukh wrote:| As they don't specify otherwise, the formula I've mentioned in the previous post holds for every p (not only prime)? |
|
In most number theory books, the variable p is reserved for primes. The formula clearly doesn't hold for n=p=4, for example.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print