Skip to content
Tutorials Center
My learning

Topics

Lesson 179 of 225 ยท Math and Bit Manipulation

Factorials, Legendre's Formula and Zeckendorf

Count trailing zeros of n!, find the power of a prime in n! with Legendre's formula, get the last nonzero digit and write numbers as sums of Fibonacci numbers.

Factorials grow absurdly fast: 25! already has 26 digits, and 1,000,000! has over five million. Yet many questions about n! have tiny answers: how many zeros end it, what is its last nonzero digit, how many times does 7 divide it? You can answer all of them without ever computing n!.

The key idea is to think in prime factors. Once you know how many copies of a prime p live inside n!, trailing zeros, divisibility and modular tricks fall out. This lesson also covers the Zeckendorf representation, a neat way to write any number as a sum of Fibonacci numbers. It builds on Number Theory and Combinatorics.

Brute force: compute n! and look

The direct method works for small n, and it makes a good reference to check cleverer code against.

Python Trailing zeros the slow way

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This breaks down when n is huge, because n! has about n log n digits.

Legendre's formula

How many times does a prime p divide n!? Among the numbers 1..n, every multiple of p contributes one factor, every multiple of p^2 contributes one more, every multiple of p^3 another, and so on. Add them up:

TEXT
v_p(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ...

That is Legendre's formula. The loop stops when p^k > n, so it takes only log_p(n) steps.

Python Legendre's formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Trailing zeros of n!

A trailing zero comes from a factor of 10 = 2 x 5. There are always more 2s than 5s in n!, so the number of zeros equals the power of 5. That is just legendre(n, 5).

Python Trailing zeros with Legendre

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line would be impossible by brute force; Legendre needs about 26 loop steps.

The smallest n whose factorial ends in k zeros

legendre(n, 5) never decreases as n grows, so you can binary search for the smallest n with at least k zeros. If the count at that n is exactly k, the answer exists. Some values of k are skipped (no factorial ends in exactly 5 zeros), because the count jumps by 2 at multiples of 25.

Python Binary search on factorial zeros

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Last nonzero digit of n!

Remove the factors of 10 and look at what remains modulo 10. A simple way: compute n! without its 2s and 5s, track those exponents, and add back the surplus 2s at the end.

Python Last nonzero digit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice pow(2, extra_twos, 10): three-argument pow does modular exponentiation (see Fast Exponentiation). This version is O(n log n); the same idea with recursion on n // 5 gives a logarithmic algorithm, but this one is easier to trust.

Factorial divisibility: is n! divisible by m?

Factor m into primes p^e. Then m divides n! exactly when legendre(n, p) >= e for every prime power in m. This avoids multiplying out the factorial.

Python Does m divide n!?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Zeckendorf's theorem

Every positive integer can be written in exactly one way as a sum of non-consecutive Fibonacci numbers (using 1, 2, 3, 5, 8, 13, ...). This is the Zeckendorf representation. Example: 100 = 89 + 8 + 3.

The greedy rule works: take the largest Fibonacci number that fits, subtract, repeat. After taking F_k the remainder is smaller than F_(k-1), so you can never pick two neighbors.

Python Zeckendorf representation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bit string never contains two 1s in a row. Because of that, the bit strings can be used as self-delimiting codes in data compression (Fibonacci coding): appending one more 1 after the last digit creates the unique "11" that marks the end of a number.

Common mistakes

  • Computing n! for big n. Use Legendre's formula; the factorial is rarely needed.
  • Counting only multiples of 5. Numbers like 25 and 125 contain several fives; keep dividing by higher powers.
  • Stopping at p * p. Legendre's loop must run while p^k <= n, not while p^k <= sqrt(n).
  • Assuming every count is reachable. Trailing-zero counts skip values (5, 11, 17, ...) because n! gains two zeros at once at multiples of 25.
  • Starting Fibonacci at 1, 1. Zeckendorf uses the distinct values 1, 2, 3, 5, ...; with a duplicate 1 the representation would not be unique.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many trailing zeros does 100! have?

    floor(100/5) + floor(100/25) = 20 + 4 = 24. Each pair (2, 5) makes a zero and fives are the scarcer factor.
  2. 2. Why do trailing zeros equal the power of 5 and not the power of 2?

    A 10 needs one 2 and one 5. Twos are plentiful, so the number of 5s decides.
  3. 3. Legendre's formula for the power of p in n! is:

    Multiples of p add one factor each, multiples of p^2 add an extra one, and so on.
  4. 4. Which of these is the Zeckendorf representation of 20?

    13 + 5 + 2 = 20 and the parts are not consecutive Fibonacci numbers. The others reuse a value or include a number that is not in the sequence.

Summary

  • Think of n! in terms of prime factors: Legendre's formula sum floor(n / p^k) gives the power of p in n! in O(log n).
  • Trailing zeros of n! equal the power of 5; binary search finds the smallest n for a given count.
  • Last nonzero digit: strip the 2s and 5s, track their counts, and re-add the extra 2s modulo 10.
  • m divides n! exactly when every prime power of m fits inside n! according to Legendre.
  • Every positive integer has a unique sum of non-consecutive Fibonacci numbers, found greedily.

Next: Fast Exponentiation