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)

1 Answers 1

5

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.

  • 0
    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!2012-03-25