0
$\begingroup$

I am looking to compute the largest integer power of $6$ that divides $73!$

If it was something smaller, like $6!$ or even $7!$, I could just use trial division on powers of $6$. However, $73!$ has $106$ decimal digits, and thus trial division isn't optimal.

Is there a smarter way to approach this problem?

$\endgroup$
  • $\begingroup$ Do you know any integer powers of $6$ that divide $73!$ ? Can you narrow down the range of possible powers that divide it, perhaps by considering the factors of $6$ ? $\endgroup$ – hardmath Oct 29 '14 at 13:28
  • $\begingroup$ Hint: You can find the largest integer power of 6 dividing 1,000,000! in a few minutes with pen and pencil. Many people can do it in their head. $\endgroup$ – gnasher729 Feb 7 '15 at 19:25
4
$\begingroup$

HINT: There are $\lfloor73/3\rfloor=24$ numbers divisible by 3, $\lfloor73/9\rfloor=8$, numbers divisible by 9, $\lfloor73/27\rfloor=2$ numbers divisible by 27 in the set $[1,73]\cap\mathbb{N}$. It should be easy now to obtain that the answer is 34 (with the value $6^{34}$).

$\endgroup$
  • 4
    $\begingroup$ This is a complete answer, not a hint... $\endgroup$ – lhf Oct 29 '14 at 13:09
  • 1
    $\begingroup$ @1hf Yesterday my student was not able to find an argument such that $\cos\varphi=1/\sqrt2$ and $\sin\varphi=-1/\sqrt2$, hence I am lost, how precise a hint should be. :-( $\endgroup$ – Przemysław Scherwentke Oct 29 '14 at 13:14
  • $\begingroup$ Ok so just to understand what you are doing, why do you take the numbers divisible by 9? $\endgroup$ – Will Oct 29 '14 at 13:30
  • $\begingroup$ @Will All $3$'s in product of prime numbers equal to $73!$ are not only from numbers divisible by 3, but also from divisible by $9=3\cdot3$ or $27=3\cdot3\cdot3$. $\endgroup$ – Przemysław Scherwentke Oct 29 '14 at 13:34
  • $\begingroup$ Ok perfect I see now what you have done. Thanks for your help $\endgroup$ – Will Oct 29 '14 at 13:47
3
$\begingroup$

Hint: $6 = 2 \cdot 3$. Since $3$ is less frequent than $2$ in the product $73! = 1 \cdot 2 \cdots 73$, count the number of factors of $3$ in the numbers $1$, $2$, $\ldots$, $73$. Note that some numbers give you more than one factor of $3$.

$\endgroup$

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.