7
$\begingroup$

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!)!$.

$\endgroup$
  • 2
    $\begingroup$ 35784728523131901147405766861593266082792328671182876288554722529113519627740074421334472433640407039999999999999999890 Hmmm. $\endgroup$ – Daniel Fischer Jan 2 '14 at 4:15
  • $\begingroup$ 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. $\endgroup$ – Mr Pie Feb 21 '18 at 5:50
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's actually $v_3((80!)!) = \frac12\cdot 80! - 110$. $\endgroup$ – Daniel Fischer Jan 2 '14 at 4:27
  • $\begingroup$ @DanielFischer Yes, we can get the error term by calculating $80!$ in base 3. $\endgroup$ – Calvin Lin Jan 2 '14 at 4:29
  • $\begingroup$ @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 :) $\endgroup$ – Calvin Lin Jan 2 '14 at 4:41
  • $\begingroup$ 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. $\endgroup$ – Matt Groff Jan 2 '14 at 21:57

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.