Difference between revisions of "Legendre's Formula"
(Added a proof) |
m (→Introductory) |
||
(18 intermediate revisions by 14 users not shown) | |||
Line 3: | Line 3: | ||
<cmath>e_p(n!)=\sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i}\right\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>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>. | + | 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>. |
− | == | + | ==Examples== |
+ | 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 === | === Part 1 === | ||
− | 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>\lfloor \frac{n}{p}\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>\lfloor \frac{n}{p^2}\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>\lfloor \frac{n}{p^3}\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. | + | 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 === | === Part 2 === | ||
− | Let the base <math>p</math> representation of <math>n</math> be < | + | 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>\ | + | * <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) |
− | <math> | + | * 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}} | {{stub}} | ||
[[Category:Number theory]] | [[Category:Number theory]] | ||
[[Category:Theorems]] | [[Category:Theorems]] | ||
[[Category:Definition]] | [[Category:Definition]] |
Latest revision as of 19:30, 7 October 2024
Legendre's Formula states that
where is a prime and
is the exponent of
in the prime factorization of
and
is the sum of the digits of
when written in base
.
Contents
[hide]Examples
Find the largest integer for which
divides
Solution 1
Using the first form of Legendre's Formula, substituting and
gives
which means that the largest integer
for which
divides
is
.
Solution 2
Using the second form of Legendre's Formula, substituting and
gives
The number
when expressed in Base-2 is
. This gives us
. Therefore,
which means that the largest integer
for which
divides
is
.
Proofs
Part 1
We use a counting argument.
We could say that is equal to the number of multiples of
less than
, or
. But the multiples of
are only counted once, when they should be counted twice. So we need to add
on. But this only counts the multiples of
twice, when we need to count them thrice. Therefore we must add a
on. We continue like this to get
. This makes sense, because the terms of this series tend to 0.
Part 2
Let the base representation of
be
where the
are digits in base
Then, the base
representation of
is
Note that the infinite sum of these numbers (which is
) is
Problems
Introductory
- Let
be a positive integer greater than 4 such that the decimal representation of
ends in
zeros and the decimal representation of
ends in
zeros. Let
denote the sum of the four least possible values of
. What is the sum of the digits of
? (2015 AMC 10B Problem 23)
- How many zeros are at the end of the base-
representation of
?
can be written as
where
and
are positive integers. What is the largest possible value of
? (BorealBear)
- Find the sum of digits of the largest positive integer n such that
ends with exactly
zeros. (demigod)
Olympiad
- Let
be numbers of factors
of the number
(that is,
and
). Find the least
such that
. (Turkey TST 1990)
This article is a stub. Help us out by expanding it.