An application of Legendre's formula

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.