Finding the Last Few Non-Zero Digits of Large Factorials

Date: 10/08/2007 at 07:27:38
From: Borislav
Subject: Last non zero digits of N!

I'm trying to find a way to find the last X non-zero digits of N! 
(factorial).  It's obvious that it can be solved while preserving the
last digits and ignoring the first.  Like this:

last 2 non-zero digits of 12! ?
1*2 = 2
2*3 = 6
6*4 = 24
24*5 = 120 (ignore last 0)
12*6 = 72
72*7 = 504 (ignore first 5)
4*8 = 32
32*9 = 288 (ignore first 2)
88*10 = 880 (ignore last 0)
88*11 = 968 (ignore first 9)
68*12 = 816 (ignore first 8) -> Answer is 16

That way we never need to multiply digits bigger than 10^(number of 
digits we need).  Is there a better way to do it?  For example what 
are the last 3 non-zero digits of 10^6! (factorial of one million). 

It seems like a problem that has a simple solution but I just cannot 
think of it.

Date: 10/08/2007 at 10:52:33
From: Doctor Vogler
Subject: Re: Last non zero digits of N!

Hi Borislav,

Thanks for writing to Dr. Math.  You're almost right.  But the last 3
nonzero digits (or non-terminal-zero digits) of 11! and 12! are 168
and 016.  The trouble is that when you drop a zero digit while
multiplying, there is another digit that appears which you haven't
calculated.  The solution is not to multiply by 10s in the first
place.  That is, suppose that n! ends in k zeros.  Then you want to
compute the last 3 digits of the integer n!/10^k.  So you divide by
5^k and 2^k whenever factors of 2 and 5 show up in n!.

So you should never multiply by any number that is divisible by 5;
instead divide by 5 first (twice or three times if necessary), and
then multiply by the quotient.  Also, for every factor of 5 that you
skip, be sure to also skip a factor of 2.  So you would end up with
something like this:

  1*2 = 002
  2*3 = 006
  6*2 = 012 (drop a 2)
  12*1 = 012 (drop a 5)
  12*6 = 072
  72*7 = 504
  504*8 = 032
  32*9 = 288
  288*1 = 288 (drop a 2*5)
  288*11 = 168
  168*12 = 016
  etc.

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 10/08/2007 at 13:53:58
From: Borislav
Subject: Last non zero digits of N!

Hi and thanks for the quick reply. 

There seems to be a misunderstanding.  My algorithm does find the 
last 2 digits of 12! as does yours.  So if I wanted to find the last 
X digits I'd keep X digits in all my multiplications, which are 
twelve in both cases.  But the question is: Is there a way to find 
the last digits without actually doing all multiplications?  For 
example to find the last 3 non-zero digits of 1000000! without 
making a million multiplications, albeit using small numbers?

Date: 10/08/2007 at 18:25:03
From: Doctor Vogler
Subject: Re: Last non zero digits of N!

Hi Borislav,

The first trick to use when N is very large is to group up numbers
with the same last digits.  In your case, after dividing out all of
the 5s from 1000000!, you get the product of all numbers NOT divisible
by 5 up to 1000000, times the product of all numbers NOT divisible by
5 up to 200000, times the product of all numbers NOT divisible by 5 up
to 40000, and so on to 8000, 1600, 320, 64, 12, and 2 (for the same
reason that the number of 5s in 1000000! is 200000 + 40000 + 8000 +
1600 + 320 + 64 + 12 + 2).  But the last 3 digits of the product of
all of the numbers from 1 to 999 not divisible by 5 is the same as the
last three digits of the product of all of the numbers from 1001 to
1999 not divisible by 5, and so on.  Figure out what this number is,
and then you can do blocks of 1000 numbers at once.  If this number is
M, then you get

  M^1000 * M^200 * M^40 * M^8 * M = M^1249

times the smaller products (up to 600, 320, 64, 12, and 2) which
require less work.  Of course, computing the last 3 digits of M^1249
can be done quickly with modular exponentiation.

Actually, you should do all of this mod 5^3 (rather than 10^3), so
that you can also divide by 2^249998 mod 5^3.  Then, since the number
of 2s in 1000000! is a lot more than 3 more than the number of 5s, you
can divide by 2^3 mod 5^3, and then multiply the result by 2^3 mod
10^3 to get the last three digits of 1000000!/10^249998.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 10/09/2007 at 04:29:30
From: Borislav
Subject: Thank you (Last non zero digits of N!)

Thank you very much!  The last reply was indeed what I was looking for.