∑MathIntermediate

Legendre's Formula

Key Points

•
Legendre's formula gives the exponent of a prime p in n! by summing how many multiples of p, $p^{2}$ , $p^{3}$ , ... $a re \leq n$ .
•
It has two equivalent forms: a sum of floors and a digit-sum identity using base-p representation of n.
•
Computing ν_p(n!) runs in O(lo $g_{p}$ n) time because the series stops once $p^{i} > n$ .
•
You can get the exponent of p in binomial coefficients via ν_p(C(n,k)) = ν_p(n!) − ν_p(k!) − ν_p((n−k)!).
•
Kummer’s theorem relates ν_p(C(n,k)) to the number of base-p carries when adding k and n−k.
•
De Polignac’s formula factorizes n! as a product over primes using Legendre’s exponents.
•
Legendre’s formula underlies algorithms for trailing zeros, divisibility tests, and modular arithmetic modulo prime powers.
•
In C++, the implementation is simple, safe, and fast, relying only on integer division and loops that shrink by factors of p.

Prerequisites

→Prime numbers and factorization — Legendre’s formula counts exponents of a prime in a factorization; understanding primes is fundamental.
→Factorials and binomial coefficients — ν_p applies to n! and C(n,k); familiarity with factorials and combinations is necessary.
→Integer division and floor function — The formula relies on repeated integer division and floor operations.
→Base representation of integers — The digit-sum form and Kummer’s theorem use base-p digits and carries.
→Sieve of Eratosthenes — De Polignac’s factorization requires enumerating primes up to n efficiently.
→Big-O notation — To analyze runtime O(log_p n) and sieve complexity O(n log log n).
→Modular arithmetic basics — Applications include divisibility and computations mod p^e.

Detailed Explanation

Tap terms for definitions

01Overview

Legendre’s formula is a classic tool for understanding how often a prime number p divides a factorial n!. Informally, n! multiplies all integers from 1 to n, and many of those factors contain p, some contain p^2, and so on. Legendre’s formula precisely counts the total number of p’s that appear in the prime factorization of n!. It does so by summing the counts of multiples of p, multiples of p^2, etc., up to n. A beautiful equivalent expression uses the base-p digits of n: the exponent equals (n minus the base-p digit sum of n) divided by (p−1). This duality connects counting multiples with positional number systems.

Algorithmically, the formula is efficient because the geometric growth of p^i makes the sum have only about log_p(n) terms. This efficiency is crucial in combinatorics and number theory applications, such as computing the highest power of a prime dividing n!, analyzing the p-adic order of binomial and multinomial coefficients, and deciding divisibility of binomials by a prime. Legendre’s formula also underlies de Polignac’s factorization of n!: n! = ∏ p^{ν_p(n!)} over all primes p ≤ n. These insights translate into compact, performant C++ implementations that scale to very large n.

02Intuition & Analogies

Imagine counting how many times you can factor out a prime p from the product 1·2·3·...·n. Every multiple of p contributes at least one p. Every multiple of p^2 contributes an additional p (beyond the one from being a multiple of p), because it contains p twice, and so on. So, if you line up all numbers from 1 to n and circle those divisible by p, then circle those divisible by p^2 (adding another count), then p^3, etc., the total number of circles each number contributes equals how many p’s are in its factorization. Adding all circles over the line is exactly Legendre’s sum.

A money analogy helps: suppose p is the value of a “bundle” (like grouping p items into a pack). If you have n items, you can make floor(n/p) full bundles of size p. Then, from the leftover single items plus the ones freed by bundling, you can make floor(n/p^2) bundles of size p^2, and so on. The total number of p-sized “units” used inside all these bundles equals the total count of p’s inside n!.

The base-p digit-sum view gives a different picture. Write n in base p. Each time you “bundle” p single units into a larger place value, you cause a carry. The total number of such carry operations across all digits measures how many p’s got absorbed into larger place values. Subtracting the sum of digits s_p(n) from n counts exactly how many items were grouped, and dividing by (p−1) converts that grouping count into the number of p’s in n!. Thus, (n − s_p(n))/(p−1) equals the same exponent as the multiple-counting method.

03Formal Definition

For a prime p and integer

n \geq 0

, the p-adic valuation of n!, denoted ν_p(n!), is the largest integer e such that

p^{e}

divides n!. Legendre’s formula states: ν_p(n!) =

\sum_{i = 1}^{\infty}

\left\lfloor

\frac{n}{p ^{i}}

\right\rfloor

, where the sum is finite because

⌊

p^{i}

⌋

= 0 once

p^{i} > n

. Equivalently, if

s_{p}

(n) denotes the sum of the digits of n written in base p, then ν_p(n!) =

\frac{n - s _{p} ( n )}{p - 1}

. This identity arises from counting carries in base-p arithmetic and provides a digit-based perspective on p-adic valuations. For binomial coefficients, ν_p

\big

(

\binom{n}{k}\big

) = ν_p(n!) − ν_p(k!) − ν_p((n−k)!). Kummer’s theorem offers a combinatorial interpretation: ν_p

\big

(

\binom{n}{k}\big

) equals the number of carries when adding k and n−k in base p. De Polignac’s formula uses Legendre’s exponents to prime-factorize n!: n! =

\prod_{p \leq n}

p^{ν_{p} (n!)}

. These relations extend naturally to multinomial coefficients by summing p-adic valuations across the factorial terms in numerator and denominator.

04When to Use

Use Legendre’s formula whenever you need the exact power of a prime dividing a factorial or a binomial/multinomial coefficient. Typical tasks include: (1) computing the largest e such that p^e | n!, (2) testing whether \binom{n}{k} is divisible by p by checking if ν_p(\binom{n}{k}) > 0, and (3) determining the number of trailing zeros of n! in base b by combining valuations for all primes in b’s factorization. In modular arithmetic, ν_p values help decide whether a factorial-based expression is zero modulo p^e.

In algorithmic contests and number-theory utilities, you will use it to factorize n! quickly (de Polignac), compare p-adic valuations to decide divisibility without computing huge numbers, and implement efficient checks for properties of binomial coefficients. If p is small relative to n, the method is extremely fast due to the logarithmic number of terms. Even for large n (up to 10^{18} or more in 64-bit computations), the loop remains short and safe, as it only divides by p each step.

Choose the floor-sum form for direct coding and the digit-sum form when you already have base-p digits or when connecting to carry-count interpretations such as Kummer’s theorem.

⚠️Common Mistakes

Using Legendre’s formula for non-prime p: the formula requires p to be prime. For composite bases, factor them into primes first and combine exponents.
Floating-point logs or powers: avoid pow/float; use integer division n /= p to prevent rounding issues and overflow.
Off-by-one errors: the sum starts at i = 1 with terms floor(n/p^i). Stop when n/p^i becomes zero. Don’t include i = 0.
Misinterpreting s_p(n): this is the digit sum of n written in base p, not in base 10. Compute digits by repeated division by p.
Forgetting that ν_p(C(n,k)) may be zero: zero means not divisible by p; negative values cannot occur if 0 ≤ k ≤ n.
Overflow fears: the running total ν_p(n!) ≤ n, so 64-bit is safe for n ≤ 2^63−1. The loop variable shrinks by p each step, so it’s stable.
Confusing Lucas’s theorem with Legendre: Lucas gives C(n,k) mod prime p using base-p digits; Legendre gives the p-adic exponent. They complement but solve different subproblems.
Ignoring all primes when factorizing n!: to factor n!, you must iterate over all primes ≤ n (sieve), then apply Legendre to each prime.

Key Formulas

Legendre’s floor-sum form

ν_{p} (n!) = i = 1 \sum \infty ⌊ \frac{n}{p ^{i}} ⌋

Explanation: Add how many multiples of p, $p^{2}$ , $p^{3}$ , ... are at most n. The sum stops when $p^{i} > n$ , so there are only $⌊ lo g_{p}$ n $⌋$ terms.

Legendre’s digit-sum form

ν_{p} (n!) = \frac{n - s _{p} ( n )}{p - 1}

Explanation: Write n in base p and sum its digits $s_{p}$ (n). Subtracting from n counts carries; dividing by p−1 converts that to the number of p factors in n!.

Binomial valuation

ν_{p} ((k n)) = ν_{p} (n!) - ν_{p} (k!) - ν_{p} ((n - k)!)

Explanation: The p-adic valuation of a binomial coefficient equals the valuation of the numerator minus that of the denominator. This enables fast divisibility tests.

Kummer via digit sums

ν_{p} ((k n)) = \frac{s _{p} ( k ) + s _{p} ( n - k ) - s _{p} ( n )}{p - 1}

Explanation: Equivalently, the number of carries when adding k and n−k in base p equals this expression. It provides a carry-counting interpretation of binomial divisibility.

De Polignac’s factorization

n! = p \leq n \prod p^{ν_{p} (n!)}

Explanation: Factor n! by taking each prime $p \leq n$ to the power ν_p(n!). This gives the complete prime factorization of n!.

Number of terms in Legendre’s sum

⌊ lo g_{p} n ⌋ = ⌊ \frac{lo g n}{lo g p} ⌋

Explanation: The number of nonzero terms in the floor-sum form equals the largest i with $p^{i} \leq n$ . This is about log base p of n.

Upper bound on ν_p(n!)

i = 1 \sum \infty ⌊ \frac{n}{p ^{i}} ⌋ \leq i = 1 \sum \infty \frac{n}{p ^{i}} = \frac{n}{p - 1}

Explanation: Replacing floors by exact fractions yields a geometric series. It shows ν_p(n!) never exceeds n/(p−1).

Trailing zeros in base b

zeros_{b} (n!) = j min ⌊ \frac{ν _{q_{j}} ( n !)}{a _{j}} ⌋ for b = j \prod q_{j}^{a_{j}}

Explanation: The number of trailing zeros of n! in base b is the minimum over primes $q_{j}$ dividing b of how many complete q_ $j^{a_{j}}$ factors fit into n!.

Multinomial valuation

ν_{p} (\frac{n !}{k _{1} ! \dots k _{m} !}) = ν_{p} (n!) - j = 1 \sum m ν_{p} (k_{j}!)

Explanation: For multinomial coefficients, p-adic valuation subtracts the sum of valuations of the denominator factorials from that of the numerator.

Complexity Analysis

For a fixed prime p and integer n, computing ν_p(n!) via Legendre’s floor-sum form runs in O(lo

g_{p}

n) time. Each iteration divides n by p, so the number of loop steps equals ⌊lo

g_{p}

n⌋, which is at most ⌊lo

g_{2}

n⌋ and typically much smaller for larger p. The space usage is O(1) because we keep a constant number of integer variables. The operations are integer divisions and additions, which are fast and exact. To compute ν_p(

(k n)

), we evaluate ν_p(n!), ν_p(k!), and ν_p(n−k!) in O(lo

g_{p}

n), O(lo

g_{p}

k), and O(lo

g_{p}

(n−k)) time, respectively. The total remains O(lo

g_{p}

n) since k and n−k are at most n. Alternatively, using Kummer’s theorem by counting carries while adding k and n−k in base p also takes O(lo

g_{p}

n) time, as it processes base-p digits of n and k. For de Polignac’s factorization of n!, we must iterate over all primes

p \leq n

. Generating primes with the Sieve of Eratosthenes costs O(n log log n) time and O(n) space. Then, for each prime p, computing ν_p(n!) costs O(lo

g_{p}

n) time. Summed over

π (n)

primes, this is roughly ∑_{

p\leqn}

O(lo

g_{p}

n), which is O(

π (n)

· log n) in the worst case but is typically dominated by the sieve for large n. In practice, for n up to around 10^7, the sieve dominates; for much larger n (where sieving is infeasible), one would not attempt full factorization of n! anyway. Across all tasks, memory stays modest (O(1) per valuation; O(n) if sieving). Integer overflow is not a concern for the valuation itself: ν_p(n!) ≤ n, so using 64-bit integers is safe provided

n \leq 2^{6} 3 - 1

. The algorithms avoid floating-point operations, ensuring numerical stability and correctness.

Code Examples

Compute ν_p(n!) using Legendre’s formula (floor-sum)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Compute nu_p(n!) = sum_{i>=1} floor(n / p^i)
5 // Assumes p is prime and n >= 0. Works for 64-bit n.
6 unsigned long long v_p_factorial(unsigned long long n, unsigned long long p) {
7     unsigned long long ans = 0;
8     while (n) {
9         n /= p;           // shrink n by factor p
10         ans += n;         // add floor(original_n / p^i)
11     }
12     return ans;
13 }
14 
15 // Compute base-p digit sum s_p(n)
16 unsigned long long digit_sum_base_p(unsigned long long n, unsigned long long p) {
17     unsigned long long s = 0;
18     while (n) {
19         s += n % p;
20         n /= p;
21     }
22     return s;
23 }
24 
25 int main() {
26     ios::sync_with_stdio(false);
27     cin.tie(nullptr);
28 
29     // Example: compute nu_5(100!) and verify with digit-sum identity
30     unsigned long long n = 100, p = 5;
31     unsigned long long v = v_p_factorial(n, p);
32     unsigned long long sp = digit_sum_base_p(n, p);
33     unsigned long long v_via_digits = (n - sp) / (p - 1);
34 
35     cout << "nu_" << p << "(" << n << "!) = " << v << "\n";
36     cout << "via digits: " << v_via_digits << "\n";
37 
38     // Multiple queries demo
39     int q; 
40     cout << "Enter number of queries: ";
41     if (!(cin >> q)) return 0;
42     while (q--) {
43         unsigned long long N, P; 
44         cin >> N >> P;
45         cout << "nu_" << P << "(" << N << "!) = " << v_p_factorial(N, P) << "\n";
46     }
47     return 0;
48 }
49

This program implements the classic floor-sum version of Legendre’s formula and a helper to compute the base-p digit sum. It demonstrates ν_5(100!) and checks the equality with the digit-sum identity. The query loop allows you to compute ν_p(n!) for arbitrary inputs quickly.

Time: O(log_p n) per querySpace: O(1)

Is C(n,k) divisible by prime p? (Legendre and Kummer)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Legendre’s valuation for n!
5 unsigned long long v_p_factorial(unsigned long long n, unsigned long long p) {
6     unsigned long long ans = 0;
7     while (n) { n /= p; ans += n; }
8     return ans;
9 }
10 
11 // nu_p(C(n,k)) via Legendre
12 unsigned long long v_p_binom_legendre(unsigned long long n, unsigned long long k, unsigned long long p) {
13     if (k > n) return 0; // conventionally 0, though binom is 0
14     return v_p_factorial(n, p) - v_p_factorial(k, p) - v_p_factorial(n - k, p);
15 }
16 
17 // Count carries when adding k and n-k in base p (Kummer)
18 unsigned long long v_p_binom_kummer(unsigned long long n, unsigned long long k, unsigned long long p) {
19     unsigned long long carries = 0, carry = 0;
20     unsigned long long a = k, b = n - k;
21     while (a > 0 || b > 0) {
22         unsigned long long da = a % p;
23         unsigned long long db = b % p;
24         unsigned long long sum = da + db + carry;
25         if (sum >= p) {
26             carries++;
27             carry = 1;
28         } else {
29             carry = 0;
30         }
31         a /= p; b /= p;
32     }
33     return carries; // equals nu_p(C(n,k))
34 }
35 
36 int main() {
37     ios::sync_with_stdio(false);
38     cin.tie(nullptr);
39 
40     // Example queries: check divisibility of C(n,k) by p
41     // Input: t, then lines of n k p
42     int t; 
43     cout << "Enter number of test cases: ";
44     if (!(cin >> t)) return 0;
45     while (t--) {
46         unsigned long long n, k, p; 
47         cin >> n >> k >> p;
48         unsigned long long v1 = v_p_binom_legendre(n, k, p);
49         unsigned long long v2 = v_p_binom_kummer(n, k, p);
50         bool divisible = (v1 > 0);
51         cout << "nu_" << p << "(C(" << n << "," << k << ")) via Legendre = " << v1 << "\n";
52         cout << "via Kummer (carries) = " << v2 << "\n";
53         cout << (divisible ? "Divisible by p" : "Not divisible by p") << "\n";
54     }
55     return 0;
56 }
57

Two independent methods compute ν_p(C(n,k)): subtraction of factorial valuations (Legendre) and counting base-p carries (Kummer). They should agree. If ν_p(C(n,k)) > 0, then p divides C(n,k). This avoids computing large factorials or binomials.

Time: O(log_p n) per test caseSpace: O(1)

Prime factorization of n! (de Polignac) using Legendre + Sieve

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Sieve of Eratosthenes to list primes up to n
5 vector<int> sieve_primes(int n) {
6     vector<bool> is_prime(n + 1, true);
7     is_prime[0] = (n >= 0);
8     if (n >= 1) is_prime[1] = false;
9     for (int i = 2; i * 1LL * i <= n; ++i) {
10         if (is_prime[i]) {
11             for (long long j = 1LL * i * i; j <= n; j += i) is_prime[(int)j] = false;
12         }
13     }
14     vector<int> primes;
15     for (int i = 2; i <= n; ++i) if (is_prime[i]) primes.push_back(i);
16     return primes;
17 }
18 
19 // Legendre valuation for n!
20 long long v_p_factorial(long long n, int p) {
21     long long ans = 0;
22     while (n) { n /= p; ans += n; }
23     return ans;
24 }
25 
26 int main() {
27     ios::sync_with_stdio(false);
28     cin.tie(nullptr);
29 
30     int n; 
31     cout << "Enter n (e.g., up to 2e6): ";
32     if (!(cin >> n)) return 0;
33     vector<int> primes = sieve_primes(n);
34 
35     // Output the prime factorization of n!
36     // n! = product over p<=n of p^{e_p}
37     for (int p : primes) {
38         long long e = v_p_factorial(n, p);
39         if (e > 0) cout << p << "^" << e << (p == primes.back() ? '\n' : ' ');
40     }
41     cout << "\n";
42     return 0;
43 }
44

This program first generates all primes ≤ n using the sieve, then applies Legendre’s formula to compute each exponent ν_p(n!). Printing p^e across all primes gives the full factorization of n! (de Polignac’s formula).

Time: O(n log log n) for the sieve + O(π(n) log n) for valuationsSpace: O(n) for the sieve; O(1) extra for valuations

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Compute nu_p(n!) = sum_{i>=1} floor(n / p^i)
5	// Assumes p is prime and n >= 0. Works for 64-bit n.
6	unsigned long long v_p_factorial(unsigned long long n, unsigned long long p) {
7	unsigned long long ans = 0;
8	while (n) {
9	n /= p; // shrink n by factor p
10	ans += n; // add floor(original_n / p^i)
11	}
12	return ans;
13	}
14
15	// Compute base-p digit sum s_p(n)
16	unsigned long long digit_sum_base_p(unsigned long long n, unsigned long long p) {
17	unsigned long long s = 0;
18	while (n) {
19	s += n % p;
20	n /= p;
21	}
22	return s;
23	}
24
25	int main() {
26	ios::sync_with_stdio(false);
27	cin.tie(nullptr);
28
29	// Example: compute nu_5(100!) and verify with digit-sum identity
30	unsigned long long n = 100, p = 5;
31	unsigned long long v = v_p_factorial(n, p);
32	unsigned long long sp = digit_sum_base_p(n, p);
33	unsigned long long v_via_digits = (n - sp) / (p - 1);
34
35	cout << "nu_" << p << "(" << n << "!) = " << v << "\n";
36	cout << "via digits: " << v_via_digits << "\n";
37
38	// Multiple queries demo
39	int q;
40	cout << "Enter number of queries: ";
41	if (!(cin >> q)) return 0;
42	while (q--) {
43	unsigned long long N, P;
44	cin >> N >> P;
45	cout << "nu_" << P << "(" << N << "!) = " << v_p_factorial(N, P) << "\n";
46	}
47	return 0;
48	}
49

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Legendre’s valuation for n!
5	unsigned long long v_p_factorial(unsigned long long n, unsigned long long p) {
6	unsigned long long ans = 0;
7	while (n) { n /= p; ans += n; }
8	return ans;
9	}
10
11	// nu_p(C(n,k)) via Legendre
12	unsigned long long v_p_binom_legendre(unsigned long long n, unsigned long long k, unsigned long long p) {
13	if (k > n) return 0; // conventionally 0, though binom is 0
14	return v_p_factorial(n, p) - v_p_factorial(k, p) - v_p_factorial(n - k, p);
15	}
16
17	// Count carries when adding k and n-k in base p (Kummer)
18	unsigned long long v_p_binom_kummer(unsigned long long n, unsigned long long k, unsigned long long p) {
19	unsigned long long carries = 0, carry = 0;
20	unsigned long long a = k, b = n - k;
21	while (a > 0 \|\| b > 0) {
22	unsigned long long da = a % p;
23	unsigned long long db = b % p;
24	unsigned long long sum = da + db + carry;
25	if (sum >= p) {
26	carries++;
27	carry = 1;
28	} else {
29	carry = 0;
30	}
31	a /= p; b /= p;
32	}
33	return carries; // equals nu_p(C(n,k))
34	}
35
36	int main() {
37	ios::sync_with_stdio(false);
38	cin.tie(nullptr);
39
40	// Example queries: check divisibility of C(n,k) by p
41	// Input: t, then lines of n k p
42	int t;
43	cout << "Enter number of test cases: ";
44	if (!(cin >> t)) return 0;
45	while (t--) {
46	unsigned long long n, k, p;
47	cin >> n >> k >> p;
48	unsigned long long v1 = v_p_binom_legendre(n, k, p);
49	unsigned long long v2 = v_p_binom_kummer(n, k, p);
50	bool divisible = (v1 > 0);
51	cout << "nu_" << p << "(C(" << n << "," << k << ")) via Legendre = " << v1 << "\n";
52	cout << "via Kummer (carries) = " << v2 << "\n";
53	cout << (divisible ? "Divisible by p" : "Not divisible by p") << "\n";
54	}
55	return 0;
56	}
57

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Sieve of Eratosthenes to list primes up to n
5	vector<int> sieve_primes(int n) {
6	vector<bool> is_prime(n + 1, true);
7	is_prime[0] = (n >= 0);
8	if (n >= 1) is_prime[1] = false;
9	for (int i = 2; i * 1LL * i <= n; ++i) {
10	if (is_prime[i]) {
11	for (long long j = 1LL * i * i; j <= n; j += i) is_prime[(int)j] = false;
12	}
13	}
14	vector<int> primes;
15	for (int i = 2; i <= n; ++i) if (is_prime[i]) primes.push_back(i);
16	return primes;
17	}
18
19	// Legendre valuation for n!
20	long long v_p_factorial(long long n, int p) {
21	long long ans = 0;
22	while (n) { n /= p; ans += n; }
23	return ans;
24	}
25
26	int main() {
27	ios::sync_with_stdio(false);
28	cin.tie(nullptr);
29
30	int n;
31	cout << "Enter n (e.g., up to 2e6): ";
32	if (!(cin >> n)) return 0;
33	vector<int> primes = sieve_primes(n);
34
35	// Output the prime factorization of n!
36	// n! = product over p<=n of p^{e_p}
37	for (int p : primes) {
38	long long e = v_p_factorial(n, p);
39	if (e > 0) cout << p << "^" << e << (p == primes.back() ? '\n' : ' ');
40	}
41	cout << "\n";
42	return 0;
43	}
44