Legendre's formula gives a formula for the largest power of a prime p that divides the factorial n!, also known as the p-adic valuation of n! and is denoted as vₚ(n!). This formula is also known as de Polignac's formula.
In particular, vₚ(n!)=⌊n/p⌋+⌊n/p²⌋+⌊n/p³⌋+⌊n/p⁴⌋+...+
This is a finite sum as ⌊n/pʲ⌋ = 0 for j>logₚ(n).
This can also be written as vₚ(n!) = (n-sₚ(n))/(p-1), where sₚ(n) is the sum of the digits when n is written in base p.
We will use this result to compute the greatest common divisor of nᵏ and n!, denoted as gcd(nᵏ, n!).
Let the prime factorization of n be Σᵢ pᵢ^eᵢ, where pᵢ are the distinct prime factors of n.
Then vₚᵢ(nᵏ) = keᵢ and thus vₚᵢ(gcd(nᵏ, n!)) = min(keᵢ, vₚᵢ(n!)). This implies that
gcd(nᵏ, n!) = ∏ₚᵢ min(keᵢ, vₚᵢ(n!))
For k = n, the values of gcd(nⁿ, n!) are listed in OEIS sequence A051696.
