Difference between revisions of "Legendre's Formula"

Latest revision as of 19:30, 7 October 2024

Legendre's Formula states that

$e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}$

where $p$ is a prime and $e_p(n!)$ is the exponent of $p$ in the prime factorization of $n!$ and $S_p(n)$ is the sum of the digits of $n$ when written in base $p$ .

Examples

Find the largest integer $k$ for which $2^k$ divides $27!$

Solution 1

Using the first form of Legendre's Formula, substituting $n=27$ and $p=2$ gives $\begin{align*}e_2(27!)=&\left\lfloor\frac{27}{2}\right\rfloor+\left\lfloor\frac{27}{2^2}\right\rfloor+\left\lfloor\frac {27}{2^3}\right\rfloor+\left\lfloor\frac{27}{2^4}\right\rfloor\\ =&13+6+3+1\\ =&23\end{align*}$ which means that the largest integer $k$ for which $2^k$ divides $27!$ is $\boxed{23}$ .

Solution 2

Using the second form of Legendre's Formula, substituting $n=27$ and $p=2$ gives $e_2(27!)=\frac{27-S_2(27)}{2-1}=27-S_2(27)$ The number $27$ when expressed in Base-2 is $11011$ . This gives us $S_2(27)=1+1+0+1+1=4$ . Therefore, $e_2(27!)=27-S_2(27)=27-4=23$ which means that the largest integer $k$ for which $2^k$ divides $27!$ is $\boxed{23}$ .

Proofs

Part 1

We use a counting argument.

We could say that $e_p(n!)$ is equal to the number of multiples of $p$ less than $n$ , or $\left\lfloor \frac{n}{p}\right\rfloor$ . But the multiples of $p^2$ are only counted once, when they should be counted twice. So we need to add $\left\lfloor \frac{n}{p^2}\right\rfloor$ on. But this only counts the multiples of $p^3$ twice, when we need to count them thrice. Therefore we must add a $\left\lfloor \frac{n}{p^3}\right\rfloor$ on. We continue like this to get $e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor$ . This makes sense, because the terms of this series tend to 0.

Part 2

Let the base $p$ representation of $n$ be $e_xe_{x-1}e_{x-2}\dots e_0$ where the $e_i$ are digits in base $p.$ Then, the base $p$ representation of $\left\lfloor \frac{n}{p^i}\right\rfloor$ is $e_xe_{x-1}\dots e_{i}.$ Note that the infinite sum of these numbers (which is $e_p(n!)$ ) is

$\begin{align*} \sum_{j=1}^{x} e_j\cdot(p^{j-1}+p^{j-2}+\cdots +1) &= \sum_{j=1}^{x} e_j \left( \frac{p^j-1}{p-1} \right) \\ &=\frac{\sum_{j=1}^{x} e_jp^j -\sum_{j=1}^{x} e_j}{p-1} \\ &=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1} \\ &=\frac{n-S_p(n)}{p-1}. \end{align*}$

Problems

Introductory

Let $n$ be a positive integer greater than 4 such that the decimal representation of $n!$ ends in $k$ zeros and the decimal representation of $(2n)!$ ends in $3k$ zeros. Let $s$ denote the sum of the four least possible values of $n$ . What is the sum of the digits of $s$ ? (2015 AMC 10B Problem 23)

How many zeros are at the end of the base- $15$ representation of $50!$ ?

$\binom{4042}{2021}+\binom{4043}{2022}$ can be written as $n\cdot 10^x$ where $n$ and $x$ are positive integers. What is the largest possible value of $x$ ? (BorealBear)

Find the sum of digits of the largest positive integer n such that $n!$ ends with exactly $100$ zeros. (demigod)

Olympiad

Let $b_m$ be numbers of factors $2$ of the number $m!$ (that is, $2^{b_m}|m!$ and $2^{b_m+1}\nmid m!$ ). Find the least $m$ such that $m-b_m = 1990$ . (Turkey TST 1990)

This article is a stub. Help us out by expanding it.

@@ Line 1: / Line 1: @@
-'''Legendre's formula''' states that
+'''Legendre's Formula''' states that
-<cmath>e_p(n)=\sum_{i\geq 1} \lfloor \dfrac{n}{p^i}\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath>
+<cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor =\frac{n-S_{p}(n)}{p-1}</cmath>
-where <math>e_p(n)</math> is the exponent of <math>p</math> in the [[prime factorization]] of <math>n!</math>, and <math>S_p(n)</math> is the sum of the digits of n when written in base <math>p</math>.
+where <math>p</math> is a prime and <math>e_p(n!)</math> is the [[exponent]] of <math>p</math> in the [[prime factorization]] of <math>n!</math> and <math>S_p(n)</math> is the [[sum]] of the [[digit]]s of <math>n</math> when written in [[base]] <math>p</math>.
-==Proof==
+==Examples==
-{{incomplete|proof}}
+Find the largest integer <math>k</math> for which <math>2^k</math> divides <math>27!</math>
+===Solution 1===
+Using the first form of Legendre's Formula, substituting <math>n=27</math> and <math>p=2</math> gives
+<cmath>\begin{align*}e_2(27!)=&\left\lfloor\frac{27}{2}\right\rfloor+\left\lfloor\frac{27}{2^2}\right\rfloor+\left\lfloor\frac {27}{2^3}\right\rfloor+\left\lfloor\frac{27}{2^4}\right\rfloor\\
+=&13+6+3+1\\
+=&23\end{align*}</cmath>
+which means that the largest integer <math>k</math> for which <math>2^k</math> divides <math>27!</math> is <math>\boxed{23}</math>.
+===Solution 2===
+Using the second form of Legendre's Formula, substituting <math>n=27</math> and <math>p=2</math> gives
+<cmath>e_2(27!)=\frac{27-S_2(27)}{2-1}=27-S_2(27)</cmath>
+The number <math>27</math> when expressed in Base-2 is <math>11011</math>. This gives us <math>S_2(27)=1+1+0+1+1=4</math>. Therefore,
+<cmath>e_2(27!)=27-S_2(27)=27-4=23</cmath>
+which means that the largest integer <math>k</math> for which <math>2^k</math> divides <math>27!</math> is <math>\boxed{23}</math>.
+==Proofs==
+=== Part 1 ===
+We use a counting argument.
+We could say that <math>e_p(n!)</math> is equal to the number of multiples of <math>p</math> less than <math>n</math>, or <math>\left\lfloor \frac{n}{p}\right\rfloor</math>. But the multiples of <math>p^2</math> are only counted once, when they should be counted twice. So we need to add <math>\left\lfloor \frac{n}{p^2}\right\rfloor</math> on. But this only counts the multiples of <math>p^3</math> twice, when we need to count them thrice. Therefore we must add a <math>\left\lfloor \frac{n}{p^3}\right\rfloor</math> on. We continue like this to get <math>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\rfloor</math>. This makes sense, because the terms of this series tend to 0.
+=== Part 2 ===
+Let the base <math>p</math> representation of <math>n</math> be <cmath>e_xe_{x-1}e_{x-2}\dots e_0</cmath> where the <math>e_i</math> are digits in base <math>p.</math> Then, the base <math>p</math> representation of <math>\left\lfloor \frac{n}{p^i}\right\rfloor</math> is <cmath>e_xe_{x-1}\dots e_{i}.</cmath> Note that the infinite sum of these numbers (which is <math>e_p(n!)</math>) is
+<cmath>\begin{align*} \sum_{j=1}^{x} e_j\cdot(p^{j-1}+p^{j-2}+\cdots +1) &= \sum_{j=1}^{x} e_j \left( \frac{p^j-1}{p-1} \right) \\
+&=\frac{\sum_{j=1}^{x} e_jp^j -\sum_{j=1}^{x} e_j}{p-1} \\
+&=\frac{(n-e_0)-(S_p(n)-e_0)}{p-1} \\
+&=\frac{n-S_p(n)}{p-1}.
+\end{align*}</cmath>
+===Problems===
+====Introductory====
+* Let <math>n</math> be a positive integer greater than 4 such that the decimal representation of <math>n!</math> ends in <math>k</math> zeros and the decimal representation of <math>(2n)!</math> ends in <math>3k</math> zeros. Let <math>s</math> denote the sum of the four least possible values of <math>n</math>. What is the sum of the digits of <math>s</math>? (2015 AMC 10B Problem 23)
+* How many zeros are at the end of the base-<math>15</math> representation of <math>50!</math>?
+* <math> \binom{4042}{2021}+\binom{4043}{2022} </math> can be written as <math> n\cdot 10^x </math> where <math> n </math> and <math> x </math> are positive integers. What is the largest possible value of <math> x </math>? (BorealBear)
+* Find the sum of digits of the largest positive integer n such that <math>n!</math> ends with exactly <math>100</math> zeros. (demigod)
+====Olympiad====
+* Let <math>b_m</math> be numbers of factors <math>2</math> of the number <math>m!</math> (that is, <math>2^{b_m}|m!</math> and <math>2^{b_m+1}\nmid m!</math>). Find the least <math>m</math> such that <math>m-b_m = 1990</math>. (Turkey TST 1990)
 {{stub}}
-[[Category:Number Theory]]
+[[Category:Number theory]]
 [[Category:Theorems]]
 [[Category:Definition]]

Page

Toolbox

Search