Detailed mathematical approach

Problem Summary

Let \(F(n)\) denote the last five non-zero digits of \(n!\). The problem asks for \(F(10^{12})\), so any method that tries to form the factorial directly is hopelessly too large.

The successful approach is to separate the trailing zeros from the rest of the factorial, compute the reduced factorial modulo \(5^5=3125\), observe what happens modulo \(2^5=32\), and then combine the two congruences into the final residue modulo \(10^5\).

Mathematical Approach

Write \(v_p(m)\) for the exponent of the prime \(p\) in \(m\). The whole computation is driven by the fact that trailing zeros come from matching one factor 2 with one factor 5.

Separate trailing zeros from the surviving digits

The number of trailing zeros in \(n!\) is the number of available factors 5, because factors 2 are more abundant. Therefore

$e=v_5(n!)=\sum_{k\ge 1}\left\lfloor \frac{n}{5^k}\right\rfloor,$

and the desired quantity is

$F(n)\equiv \frac{n!}{10^e}\pmod{100000}.$

This identity says exactly what must be preserved: remove the \(e\) matched pairs \((2,5)\), keep everything else, and then read the result modulo \(10^5\).

Remove all factors of 5 recursively

It is convenient to strip out the factors of 5 first and delay the matching factors of 2 until later. Define

$U(n)=\prod_{m=1}^{n}\frac{m}{5^{v_5(m)}}.$

Then \(U(n)=n!/5^e\). Split the product into terms not divisible by 5 and terms of the form \(5q\):

$U(n)=\left(\prod_{\substack{1\le m\le n\\ 5\nmid m}} m\right)\left(\prod_{q=1}^{\lfloor n/5\rfloor}\frac{q}{5^{v_5(q)}}\right).$

The second factor is exactly \(U(\lfloor n/5\rfloor)\). If we define

$A(n)=\prod_{\substack{1\le m\le n\\ 5\nmid m}} m \pmod{3125},$

then the key recurrence becomes

$U(n)\equiv A(n)\,U\!\left(\left\lfloor\frac{n}{5}\right\rfloor\right)\pmod{3125}.$

Each recursive step removes one layer of factor 5 from every multiple of 5. Repeating the step until the argument reaches 0 accounts for all powers of 5 in the factorial.

Exploit the 3125-block periodicity

Write \(n=3125q+r\) with \(0\le r<3125\). Inside one full block of length 3125, the numbers not divisible by 5 form a complete reduced residue system modulo \(3125\). For an odd prime power, the product of all units is \(-1\) modulo that power, so

$A(n)\equiv (-1)^q A(r)\pmod{3125}.$

This is why the implementations precompute only one prefix table for a single block. Every complete block contributes either \(1\) or \(-1\), depending on whether \(q\) is even or odd, and the leftover part contributes one table lookup.

Divide out the matched twos modulo \(3125\)

Since \(U(n)=n!/5^e\), one more adjustment is needed to remove the matching factor \(2^e\):

$R_{3125}\equiv U(n)\,2^{-e}\pmod{3125}.$

Because \(2\) is invertible modulo \(3125\) and \(\varphi(3125)=2500\), Euler's theorem allows the exponent of 2 to be reduced modulo 2500 when the inverse power is computed.

At this point \(R_{3125}\) is exactly the reduced factorial modulo \(5^5\).

Recover the residue modulo \(10^5\) with CRT

The modulus \(100000\) factors as

$100000=32\cdot 3125.$

We already know the residue modulo 3125. On the modulo 32 side, the surviving power of 2 is

$v_2(n!)-v_5(n!).$

For large \(n\), and in particular for \(n=10^{12}\), this quantity is at least 5, so the reduced factorial is divisible by 32. Therefore the final answer is the unique solution of

$x\equiv R_{3125}\pmod{3125},\qquad x\equiv 0\pmod{32}.$

The implementations solve this by writing \(x=R_{3125}+3125k\) and choosing the unique \(k\pmod{32}\) that makes the second congruence true. Small values of \(n\) are handled directly so that this large-\(n\) shortcut is used only where it is valid.

Worked example: \(n=10\)

Here

$e=v_5(10!)=\left\lfloor\frac{10}{5}\right\rfloor=2.$

After removing all factors of 5 from the numbers \(1,2,\dots,10\), the remaining factors are

$1,2,3,4,1,6,7,8,9,2.$

So

$U(10)=1\cdot 2\cdot 3\cdot 4\cdot 1\cdot 6\cdot 7\cdot 8\cdot 9\cdot 2=145152.$

Now divide by the matching factor \(2^2\):

$\frac{U(10)}{2^2}=36288.$

Thus the last five non-zero digits of \(10!\) are \(36288\), which is the small case used to verify the method.

How the Code Works

One-time preprocessing modulo \(3125\)

The C++, Python, and Java implementations begin by building a prefix table of products of positive integers that are not divisible by 5, reduced modulo 3125. Entry \(i\) stores the product of all such integers up to \(i\), so any remainder block can be answered immediately.

Recursive evaluation of the reduced factorial

The main evaluator repeatedly replaces \(n\) by \(\lfloor n/5\rfloor\). At each level it determines how many complete blocks of length 3125 occur, applies the sign \((-1)^q\), multiplies by the stored prefix product for the leftover block, and then recurses. A separate loop computes \(v_5(n!)\) from Legendre's formula.

Inverse power of 2 and CRT reconstruction

After the recursion returns the value of \(U(n)\) modulo 3125, the implementation multiplies by the modular inverse of \(2^e\) to obtain the reduced factorial modulo \(3125\). It then lifts this residue to modulo \(100000\) by enforcing the condition modulo 32. For tiny inputs, the implementations also keep a direct multiplication branch, which doubles as an easy correctness check.

Complexity Analysis

The prefix table has length 3125, so its construction is a fixed one-time cost. The recursive stage divides \(n\) by 5 at each step, giving \(O(\log_5 n)\) levels, and each level performs only constant-time modular arithmetic.

Thus the running time for one query is \(O(\log n)\) after constant-size preprocessing, and the extra memory usage is \(O(\log n)\) for the recursive call stack, or \(O(1)\) extra space if the same recurrence is written iteratively. In concrete terms, the algorithm is fast because it never touches more than a handful of base-5 levels even when \(n=10^{12}\).

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=160
2. Legendre's formula: https://en.wikipedia.org/wiki/Legendre%27s_formula
3. Euler's theorem: https://en.wikipedia.org/wiki/Euler%27s_theorem
4. Chinese remainder theorem: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
5. Multiplicative group of integers modulo \(n\): https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n