Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Q. For what maximum value of $n$ will the expression $\frac{10200!}{504^n}$ be an integer? I have the solution to this question and I would like you to please go through the solution below. My doubt follows the solution :)

The solution can be found by writing $504 = 2^3 \cdot 3^2 \cdot 7$ and then finding the number of $2^3$s, $3^2$s and $7$s in the numerator, which can be obtained by

Number of $2$s = $\left\lfloor\frac{10200}{2}\right\rfloor + \left\lfloor\frac{10200}{2^2}\right\rfloor + \left\lfloor\frac{10200}{2^3}\right\rfloor + \dots + \left\lfloor\frac{10200}{2^{13}}\right\rfloor= 10192$ where $\left\lfloor\dots\right\rfloor$ is the floor function.

Therefore, the number of $2^3\textrm{s} = \left\lfloor\frac{10192}{3}\right\rfloor = 3397$

$\begin{align}\textrm{Similarly, the number of }3^2\textrm{s} &= 2457\\ \textrm{and the number of }7\textrm{s} & = 1698\end{align}$

The number of factors of $2^3 \cdot 3^2 \cdot 7$ is clearly constrained by the number of $7$s, therefore $n = 1698$.

My question is, whether there is any way I can simply look at the prime factors of the divisor and know which prime factor is going to be the constraining factor? (as $7$ was, in this particular example)

share|improve this question
add comment

1 Answer

In this answer, it is shown that the number of factors of $p$ in $n!$ is $$ \frac{n-\sigma_p(n)}{p-1}\tag{1} $$ where $\sigma_p(n)$ is the sum of the base-$p$ digits of $n$.

Factor $$ 504=2^3\cdot3^2\cdot7\tag{2} $$ Write $10200$ in base-$2$, base-$3$, and base-$7$: $$ \begin{array}{}10011111011000_2&111222210_3&41511_7\end{array}\tag{3} $$ The number of factors of $2$ in $10200!$ is $\frac{10200-8}{2-1}=10192$.

The number of factors of $3$ in $10200!$ is $\frac{10200-12}{3-1}=5094$.

The number of factors of $7$ in $10200!$ is $\frac{10200-12}{7-1}=1698$.

Since $\left\lfloor\frac{10192}{3}\right\rfloor=3397$, $\left\lfloor\frac{5094}{2}\right\rfloor=2547$, and $\left\lfloor\frac{1698}{1}\right\rfloor=1698$, the maximum value of $n$ so that $\frac{10200!}{504^n}$ is an integer is $n=1698$.

To answer the question asked:

For large $n$, the sum of the digits of $n$ is small compared to $n$, so suppose $$ d=p_1^{e_1}p_2^{e_2}\dots p_m^{e_m}\tag{4} $$ Following the computations above, the greatest power of $d$ that divides $n!$ is $$ \min_k \left\lfloor\frac{n-\sigma_{p_k}(n)}{e_k(p_k-1)}\right\rfloor\tag{5} $$ Ignoring $\sigma_{p_k}(n)$ as negligible, the greatest of $e_k(p_k-1)$ is a strong indicator of which $p_k$ is the constraining factor.

In the current case, the greatest of $3(2-1)=3$, $2(3-1)=4$, and $1(7-1)=6$ hints strongly that $7$ is the constraining factor.

share|improve this answer
    
Thanks for the answer Rob!! The last statement should probably have been "In the current case, the greatest of 3(2−1)=3, 2(3−1)=4, and $1(7−1)=6$ hints strongly that 7 is the constraining factor." Well thanks again! Much appreciated! –  BumbleBee Mar 25 '12 at 14:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.