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.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.