# Max value of $n$ for which $3^n\mid(80!)!$

Calculate the max value of $n$ for which $(80!)!$ is divisible by $3^n$.

My Attempt:

The exponent of prime factor $p$ in $(n!)$ is given as

$$v_p(n!) = \left\lfloor \frac{n}{p}\right\rfloor + \left\lfloor \frac{n}{p^2}\right\rfloor+\left\lfloor \frac{n}{p^3}\right\rfloor+\left\lfloor \frac{n}{p^4}\right\rfloor+\cdots$$

So the exponent of prime factor $3$ in $(80!)$ is given as

$$v_3(80!) = \left\lfloor \frac{80}{3}\right\rfloor +\left\lfloor \frac{80}{3^2}\right\rfloor+\left\lfloor \frac{80}{3^3}\right\rfloor+\left\lfloor \frac{80}{3^4}\right\rfloor+\cdots=36$$

But I do not understand how to calculate exponent of $3$ in $(80!)!$.

• 35784728523131901147405766861593266082792328671182876288554722529113519627740074421334472433640407039999999999999999890 Hmmm. – Daniel Fischer Jan 2 '14 at 4:15
• The algebraic expression $(80!)!$ doesn't look pretty, and $80!!$ is something different. Maybe we can let $80!_n = ((80!)!)!\ldots\, n$ times? Well, I'm keeping that. – Mr Pie Feb 21 '18 at 5:50

The exact answer will be $v_3 ( (80!)!) = \lfloor \frac{80!}{3} \rfloor + \lfloor \frac{80!}{3^2} \rfloor + \ldots$.

If we ignore the floor function, and take the sum of the geometric progression to infinity, the answer would simply be

$$v_3 ((80!)!) \approx \frac{ 80!}{3} + \frac{80!}{3^2} + \ldots = 80! \times \frac{ \frac{1}{3} } { \frac{2}{3} } = \frac{80!}{2}.$$

Since you already calculated that $v_3 ( 80!) = 36$, we know that the first 36 terms of the summation are integers, and the rest of the terms will thus contribute a very small error. In fact, we can hunt down the exact value of this error, by looking at the base 3 representation of $80!$.

Claim: $v_3 (n!) = \frac{n}{2} - R$ where $R$ is half the digit sum of $n$ in base 3.

Proof: This follows immediately by looking at the overestimation in each digit, which is $(0.1111111\ldots)_3 = \frac{1}{2}$. Hence the total overestimation is half the digit sum in base 3. $_\square$

As an explicit example, if we look at $v_3 (80!) = (222)_3 + (22)_3 + (2)_3$, we have over approximated by $2 \times \frac{1}{2} + 2 \times \frac{1}{2} + 2 \times \frac{1}{2} + 2 \times \frac{1}{2} = 4$. A quick check shows that $\frac{80}{2} - 4 = 36$, which agrees with your calculation.

It remains to show that $80!$ in base 3 has a digit sum of 220 (I don't know of an immediate way to do this), which would give you Daniel's result that $v_3 (80!) = \frac{80!}{2} - 110$.

Of course, this easily generalizes to other (prime) values.

• It's actually $v_3((80!)!) = \frac12\cdot 80! - 110$. – Daniel Fischer Jan 2 '14 at 4:27
• @DanielFischer Yes, we can get the error term by calculating $80!$ in base 3. – Calvin Lin Jan 2 '14 at 4:29
• @DanielFischer Thanks! That allowed me to make it into a much more complete answer. I did this a long time back, and just remembered it :) – Calvin Lin Jan 2 '14 at 4:41
• As to showing that $80!$ in base 3, note that $\prod_k{ \left( 1 + a x^{3^k}+a^2 x^{2 \cdot 3^k} \right) }$ gives the generating function for the sum of numbers in base 3. In other words, this function gives $a^\text{count}\cdot x^n$ for each $n$, where count is the sum of the digits in base 3. We may be able to extract this term from the generating function. – Matt Groff Jan 2 '14 at 21:57