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)
