Last non-zero digits of a very large factorial

Question

How can one calculate the last few non-zero digits of a factorial of a large number?

By large, i mean like n=10^100 or something
(EDIT : 10^100 is the magnitude of 'n' in n! )
By few, i mean till 7-8...

I tried googling it and found this -

Last non-zero digit of a factorial

I tried to expand this to last 2 non-zero digits or more, but failed...

I found other websites on google that showed how to calculate last x number of digits but it wasn't clear and i wasn't able to understand it...

Can anyone help me with this?

Also, am not able to get this, the last two non-zero digits of 99! are 64, so i figured that the last two non-zero digits of (199! / 99!) should also be 64, but they turn out to be 24, i know i am making an extremely big logical mistake in this one, am just not able to put my finger on it!

Answer 1

The trick to do your calculations is that you want to find 3 numbers.

1. The number of factors of 5 in the answer.
2. The number of factors of 2 in the answer.
3. The last few digits of all of the products of all of the other primes in the answer.

The number of factors of 5 give you the number of factors of 10. Then subtract the number of factors of 2 from the number of factors of 5. Figure out the last few digits of 2 to that power. Multiply that by the last few digits found in step 3, and you're done.

The number of factors of 5 can be worked out as follows. Take n/5 (round down). That's how many have a first factor of 5. Then n/25 (round down). That how many have a second factor of 5. Continue until you're done.

The number of factors of 2 can be worked out similarly only with the sequence 2, 4, 8, 16 instead.

The third part is tricky.

But what is easier is to do is figure out the product of all of the numbers up to and including n which are relatively prime to 2 and 5. Call that function f(n). You can calculating it by multiplying the relatively prime numbers mod 10^k. And take advantage of the fact that f(i * 10^k + j) = f(j) mod(10^k).

Then you want the last few digits of f(n)*f(n/2)*f(n/4)*f(n/5)*f(n/8)*f(n/10)*f(n/16)*.... Producing that sequence efficiently is a version of the Hamming Numbers problem. See https://rosettacode.org/wiki/Hamming_numbers for how to do that. For 10^100 there will still only be tens of thousands in this sequence - it is well under control.

---

For your second question about ratios, you'll need to take advantage of the following two facts. Fact 1 is that you know the right number of factors of 2 and 5 just through subtraction. The second is that if m is relatively prime to 10 then m * m^(4 * 10^(k-1) - 1) is 1 mod 10^k. So you can now "divide" mod 10^k, and figure out the last few terms of every factor of the answer that doesn't involve a 2 or a 5, then figure out the number of 0s, and the number of leftover factors of 2 or 5 that you have.

---

Here is a significant optimization. If you know f(n) mod 2^8 and 5^8, it isn't hard to figure it out mod 10^8. But its value mod those two can be reduced to a lookup table of modest size. The larger one you only need to store it for odd n up to 4*390625, but there are less than 800k of those. (At that point you've multiplied by all elements of the group of things not divisible by 5 mod 5^8, and that product is 1. Then the pattern repeats.) If you're using 4 byte integers, that's few MB lookup table that can be precalculated fairly easily.

I should probably explain why this trick works, because it isn't obvious and I got it wrong a couple of times. The trick is that the numbers relatively prime to 5^k form a group. Meaning each has an inverse. So if you multiply them all out, and rearrange, each has an inverse EXCEPT 5^k-1. So multiply by another copy and they pair up again including that pesky one and the product comes out to 1. Now for our f we are only interested in odd numbers not divisible by 5, but the odd ones not divisible by 5 out to 2*5^k are, mod 5^k, just a rearrangement of the ones divisible by 5 out to 5^k. We need 2 copies, hence out to 4*5^k. But we only need the odds because the even right after always has the same value as the previous odd.

---

Per request, here is how this works for a single example. I'll do the last 3 digits of 15!

15! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12 * 13 * 14 * 15
    = (1*3*7*9*11*13) * (2*6*14) * (4*12) * (5*15) * (8) * (10)
    = (1*3*7*9*11*13) * 2^3*(1*3*7) * 2^4*(1*3) * 5^2*(1*3) * 2^3*(1) * 10*(1)
    = 2^11 * 5^3 * f(15) * f(15/2) * f(15/4) * f(15/5) * f(15/8) * f(15/10)
    = 2^11 * 5^3 * f(15) * f(15/2) * f(15/4) * f(15/5) * f(15/8) * f(15/10)
    = 10^3 * 2^8 * f(15) * f(7) * f(3) * f(3) * f(1) * f(1)
    Which leads to the calculation...
             256 *   27  *  21  *   3  *   3  *   1  *   1 (mod 1000)
                                                     = 368 (mod 1000)

This is correct because 15! = 1307674368000.