Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|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

Your Answer


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.