wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Last nonzero digit of n!
        
(Message started by: Eigenray on Nov 3^rd, 2003, 9:32am)

Title: Last nonzero digit of n!
Post by Eigenray on Nov 3^rd, 2003, 9:32am

Determine the last nonzero digit of 1,000,000,000! (without using a computer).

Title: Re: Last nonzero digit of n!
Post by aero_guy on Nov 3^rd, 2003, 12:03pm

~[hide]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.[/hide]~

Title: Re: Last nonzero digit of n!
Post by Rezyk on Nov 3^rd, 2003, 2:08pm

on 11/03/03 at 12:03:07, 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.

Title: Re: Last nonzero digit of n!
Post by Barukh on Nov 4^th, 2003, 4:43am

That's what I got:
[smiley=blacksquare.gif]
[hide]4, followed by 249999998 zeros.[/hide]
[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...

Title: Re: Last nonzero digit of n!
Post by Icarus on Nov 4^th, 2003, 10:00am

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.

Title: Re: Last nonzero digit of n!
Post by SWF on Nov 4^th, 2003, 7:15pm

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.

Title: Re: Last nonzero digit of n!
Post by Eigenray on Nov 5^th, 2003, 12:42am

If F(n) = last nonzero digit of n!, then I come up with: [hide]for 0[le]r<5,
F(5d+r) = r! 2^d F(d) (mod 5)
Knowing F mod 5 is sufficient, because we also know it must be even[/hide].

Barukh, how did you do it?

Title: Re: Last nonzero digit of n!
Post by Barukh on Nov 5^th, 2003, 2:20am

Bravo, Eigenray!! You’ve got the idea!

on 11/05/03 at 00:42:10, Eigenray wrote:

Barukh, how did you do it?

[hide]Let E(n, p) be the maximal power of p that divides n! (e.g. E(8, 2) = 7). Let p_m…p₀ be the representation of n in radix p. Then the following holds (Source: Graham et al, "Concrete mathematics", ex. 4.40):

n! / p^{E(n, p)} = (-1) ^{E(n, p)} p_m! … p₀! (mod p).
E(n,p) is computed as [sum]_k>0 [smiley=lfloor.gif] n / p^k [smiley=rfloor.gif]. Put p=5 to get the required digit.[/hide]

I wish to know whether a more elegant derivation exists...

Title: Re: Last nonzero digit of n!
Post by Eigenray on Nov 5^th, 2003, 3:44am

I originally saw this listed somewhere as a computing exercise, but it seemed doable by hand. Here's how I got that recurrance:[hide]
Let E(n) = number of times 5 divides n! = number of times 10 divides n!. Then we're looking for n!/10^E modulo 10, so it's sufficient to find G(n):= n!/5^E mod 5. Let n=5d+r, and consider:
G(n) = n!/5^E(n)
= (1...4)[5](6...9)[10].....[5d](1...r)/5^E(n)
= 4!^d 5^d d! r!/5^E(n) = (-1)^d r! d!/5^E(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!/10^E = G(n)/2^E, replace (-1) with (-1) 2^-1=2 to get a formula for F[/hide].

Title: Re: Last nonzero digit of n!
Post by Barukh on Nov 6^th, 2003, 2:17am

Really elegant derivation, Eigenray! Especially, I liked the relation: [hide]E(n) = E(d) + d[/hide]. :)

on 11/05/03 at 03:44:51, 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)?

Title: Re: Last nonzero digit of n!
Post by Eigenray on Nov 7^th, 2003, 2:42am

on 11/06/03 at 02:17:54, 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.