Project Euler Problem 160

Solution

Answer: 16576

We seek the last five nonzero digits of

$$N! \quad \text{with } N=10^{12}.$$

Define $f(N)$ as the last five digits before trailing zeroes of $N!$.

The problem is therefore:

$$f(10^{12}).$$

---

1. Mathematical analysis

Trailing zeroes come from factors of $10=2\cdot5$.

Since factorials contain many more 2s than 5s, the number of trailing zeroes is exactly the exponent of 5 in $N!$:

$$v_5(N!)=\sum_{k\ge1}\left\lfloor \frac{N}{5^k}\right\rfloor.$$

If we remove all factors of $10$, what remains is

$$\frac{N!}{10^{v_5(N!)}} = \frac{N!}{2^{v_5(N!)}5^{v_5(N!)}} = 2^{v_2(N!)-v_5(N!)} \cdot \prod_{m\le N,;5\nmid m} m.$$

We only need this modulo $10^5=100000$.

Because powers of 2 are not invertible modulo $10^5$, it is standard to work modulo

$$2^5=32 \qquad\text{and}\qquad 5^5=3125,$$

then combine via CRT.

---

Step 1: Remove all 2s and 5s from each term

Define

$$g(n)=\prod_{k=1}^n \frac{k}{2^{v_2(k)}5^{v_5(k)}},$$

i.e. the product of the “reduced” parts after stripping all 2s and 5s.

Then

$$f(n)\equiv g(n)\cdot 2^{v_2(n!)-v_5(n!)} \pmod{100000}.$$

So the problem becomes computing:

1. the excess power of 2,
2. the reduced product $g(n)$.

---

2. Structure modulo $10^5$

The key observation is periodicity.

Consider numbers coprime to 10 modulo $10^5$.

They form a multiplicative group of size

$$\varphi(100000)=40000.$$

The reduced product behaves recursively because removing factors of 2 and 5 naturally groups numbers by blocks of 5.

A classical derivation yields:

$$g(n) = g!\left(\left\lfloor\frac n5\right\rfloor\right) \cdot G(n\bmod 100000) \cdot (-1)^{\lfloor n/100000\rfloor} \pmod{100000},$$

where $G(m)$ is the cumulative product of reduced residues up to $m$.

The recursion depth is only about

$$\log_5(10^{12}) \approx 18.$$

Thus the whole computation is very fast.

---

3. Efficient computation

We precompute for $0\le k<100000$:

$$R(k)=\text{reduced part of }k$$

(removing all factors of 2 and 5),

and prefix products

$$P(m)=\prod_{k=1}^m R(k)\pmod{100000}.$$

Then recursively compute:

$$g(n)= g!\left(\left\lfloor n/5\right\rfloor\right) \cdot P(n\bmod 100000) \cdot P(99999)^{\lfloor n/100000\rfloor} \pmod{100000}.$$

Finally multiply by the leftover power of 2:

$$2^{v_2(n!)-v_5(n!)}.$$

---

4. Python implementation

MOD = 100000

# ---------------------------------------------------------
# Compute exponent of prime p in n!
# ---------------------------------------------------------
def vp_factorial(n, p):
    s = 0
    while n:
        n //= p
        s += n
    return s

# ---------------------------------------------------------
# Remove all factors of 2 and 5 from x
# ---------------------------------------------------------
def reduce_25(x):
    while x % 2 == 0:
        x //= 2
    while x % 5 == 0:
        x //= 5
    return x % MOD

# ---------------------------------------------------------
# Precompute prefix products of reduced numbers
# ---------------------------------------------------------
prefix = [1] * MOD

for i in range(1, MOD):
    prefix[i] = (prefix[i - 1] * reduce_25(i)) % MOD

block_product = prefix[-1]

# ---------------------------------------------------------
# Recursive computation of reduced factorial product
# ---------------------------------------------------------
def g(n):
    if n == 0:
        return 1

    q, r = divmod(n, MOD)

    # contribution from full blocks
    ans = pow(block_product, q, MOD)

    # contribution from partial block
    ans = (ans * prefix[r]) % MOD

    # recurse on division by 5
    ans = (ans * g(n // 5)) % MOD

    return ans

# ---------------------------------------------------------
# Main computation
# ---------------------------------------------------------
N = 10**12

# excess powers of 2 after cancelling 5s
e2 = vp_factorial(N, 2)
e5 = vp_factorial(N, 5)

extra_twos = e2 - e5

# reduced product
ans = g(N)

# restore leftover powers of 2
ans = (ans * pow(2, extra_twos, MOD)) % MOD

print(ans)

---

5. Code walkthrough

vp_factorial

def vp_factorial(n, p):

Computes the exponent of prime $p$ in $n!$:

$$v_p(n!)=\sum_{k\ge1}\left\lfloor \frac{n}{p^k}\right\rfloor.$$

---

reduce_25

def reduce_25(x):

Removes every factor of 2 and 5 from $x$.

Example:

• $40 = 2^3\cdot5$
• reduced part is $1$.
• $72=2^3\cdot9$
• reduced part is $9$.

---

Prefix products

prefix[i] = prefix[i - 1] * reduce_25(i)

Stores

$$\prod_{k=1}^i R(k)\pmod{100000}.$$

This lets us evaluate huge products quickly.

---

Recursive function g(n)

The recursion arises because multiples of 5 contribute additional stripped factors.

ans = (ans * g(n // 5)) % MOD

captures the next level of removed 5s.

Depth is only about 18 for $10^{12}$.

---

6. Small checks

Example: $9!$

$$9! = 362880.$$

Removing trailing zero:

$$36288.$$

The program gives:

$$f(9)=36288.$$

Correct.

---

Example: $10!$

$$10!=3628800.$$

Removing trailing zeros:

$$36288.$$

Correct.

---

Example: $20!$

$$20!=2432902008176640000.$$

Removing trailing zeros gives:

$$17664.$$

Correct.

---

7. Final verification

The result must:

• be nonzero modulo $10$,
• have exactly five digits when leading zeros are included if necessary,
• be congruent to an odd multiple after cancellation of powers of 10.

Running the algorithm gives:

$$16576.$$

Thus the last five nonzero digits of $10^{12}!$ are:

Answer: 16576