# Last digits of factorial

Yes, this is an attempt to understand why my solution for Project Euler problem 160 isn't working. I hesitate to post my code lest I offer a solution to someone else.

The problem is to find the last n non-zero digits of a factorial. In this case, 5 digits.

I factorize all numbers from 2 to 100,000

For example, for n=9: 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9

would be:

2^7 3^4 5^1 7^1

cancelling all the powers of 5 with corresponding 2s:

2^6 3^4 7^1

I tested on 9! 10! 11! 12! 13! 20! and got the last 5 digits. I tried 100,000! and got the same number that I had achieved by a different method: 62496 This made me realize that even though the pattern repeats, I must multiply them together.

Since 10^12 = 10^5 * 10^7

the answer should require computing the answer I get for 100,000! to the power 10^7.

powermod(62496, 1e7, m)

where m is the modulo 10^5 to take out the low m digits.

I think I'm on the right track here, but since Project Euler tells me I'm wrong, my question is am I missing some bookkeeping thing, or is my approach flawed?

My new approach is to consider each terminating digit:

1 2 3 4 5 6 7 8 9

All numbers ending in 1 just multiply:

prod = 1
for i = 1 to 1 trillion stepping by 10
prod = (prod * (i mod m) ) mod m
powers2 += 4; // account for 2, 4, 6, 8 (can pull this out of the loop)
d2 = (i+1)/2
prod = (prod * (i mod m) ) mod m

same for d3, d4, d6, d7, d8.  Evens get divided by 2

d5 = (i+4) / 5
while (d5 mod 5 == 0)
powers5++
d5 /= 5
end while

d10 = (i+9)/10
while (d10 mod 5 == 0)
powers5++
d10 /= 5
end while
end

powers2 = powers2 - powers5
prod = (prod * powermod(2, power2, m)) mod m


I evidently didn't get the right answer, is this concept flawed too?

Could I have combined these two concepts? I still don't see why I care about any high digits. They don't affect low digits. I do, however, need to account for extra powers of 5 resulting in more zeros. Could I just do brute force for numbers ending in 5 and 10, find out how many there are and cancel with just enough from numbers ending in 2, but do the remaining ones by multiplying all the digits from 1 to 100000? The bookkeeping of that seems complicated, and I still have to multiply 3/10 of the trillion numbers so it's not ideal.

Alternatively, can I consider all multiples of 5^2, 5^3 .. 5^17, and 2^2 2^3 ... 2^k? All I need is to pull those out, right?

How about counting all multiples of powers of 5 greater than 100,000? I can eliminate all powers of 2 in the multiplication of 1 to 100,000. Then

5^8 = 390625

There are 10^12 / 5^8 of these in the set. That should cover 5^9 and beyond as well, since anything that is a multiple of 5^8 is also a multiple of 5^9, 5^10, etc.

I get 2560000 multiples of 5^8. But 5^9 is one more 5, so:

total number of 5s: 10^12 / 5^8 = 2560000 10^12 / 5^9 = 512000 10^12 / 5^10 = 102400 10^12 / 5^11 = 20480 10^12 / 5^12 = 4096 10^12 / 5^13 = 819 10^12 / 5^14 = 163 32 6 1

Total multiples of 5: 2560000+512000+102400+20480+4096+819+163+32+6+1

So if I multiply 1 to 100,000 mod 100,000 removing all multiples of 5, and remove enough powers of 2 so that when I take it to the power:

powers5 = 2560000+512000+102400+20480+4096+819+163+32+6+1
prod = multmod(1 to 100,000, modulo 100,000)  // factoring out 5s and 2s
prod = powermod(prod, 10^7, mod 100,000)

powers2 = powers2 * 10^7
powers2 = powers2 - powers5

prod = prod * powermod(2, powers2, mod 100000)

-

Since this is Project Euler I won't give a solution. However I will point out the (hopefully obvious) fact that you won't be able to solve this by considering all primes less than $10^{12}$, so you will need a different approach.
What happens when you try this for 30! ? (The difference being that $20 < 5^2 < 30$.) –  universalset Dec 6 '13 at 3:17
Let's make a few observations: (a) If I didn't have to worry about multiples of 2 and 5 (let's pretend I wasn't even including them in the product) then I could just count the numbers of factors with each remainder (mod $10^5$) in the product, and then exponentiate for each such remainder (mod $10^5$) and then take the product of the results (mod $10^5$). (b) I do care about numbers which are multiples of 2 and 5. Perhaps I can somehow "strip off" the prime factors of 2 and 5 from these numbers and let the results contribute to the counts above. (c) Now I have to deal with the 2s and 5s. –  universalset Dec 14 '13 at 1:45