4
$\begingroup$

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)

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – BumbleBee Mar 25 '12 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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