Legendre's formula gives the exponent of a prime p in the prime factorization of a factorial n!, expressing it as the sum over k of the floor of n divided by p to the power k. Equivalently, it can be computed from the sum of the base-p digits of n, subtracted from n and divided by p minus 1. The formula is a basic tool in number theory and combinatorics for determining how many trailing zeros a factorial has in a given base, since the number of trailing zeros in base 10 depends on the exponent of 5 dividing n!.
Facts
Connections
Attributed To
Source Legendre's Formula (Wikipedia)
In Branch
Source Wolfram MathWorld: Legendre's Formula
Is Kind Of Object
Named After
Sources
1. Legendre's Formula (Wikipedia)
Lead sectionQuote, Lead section
In mathematics, Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial n!. It is named after Adrien-Marie Legendre.
Wolfram MathWorld: Legendre's Formula
Wolfram MathWorldIn Branch: Number Theory, Subject classificationsQuote, In Branch: Number Theory, Subject classifications
Number Theory Prime Numbers
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.