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$
2
  • $\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
    Commented Oct 29, 2014 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
    Commented Feb 7, 2015 at 19:25

2 Answers 2

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$
5
  • 4
    $\begingroup$ This is a complete answer, not a hint... $\endgroup$
    – lhf
    Commented Oct 29, 2014 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$ Commented Oct 29, 2014 at 13:14
  • $\begingroup$ Ok so just to understand what you are doing, why do you take the numbers divisible by 9? $\endgroup$
    – Will
    Commented Oct 29, 2014 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$ Commented Oct 29, 2014 at 13:34
  • $\begingroup$ Ok perfect I see now what you have done. Thanks for your help $\endgroup$
    – Will
    Commented Oct 29, 2014 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .