# Factorial Divisors

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 Answer

In the section Counting Prime Factors of n!, 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.

-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 52, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.950000524520874, "perplexity_flag": "head"}