Compute largest integer power of $6$ that divides $73!$

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?

• 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$ ? – hardmath Oct 29 '14 at 13:28
• 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. – gnasher729 Feb 7 '15 at 19:25

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}$).
• @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. :-( – Przemysław Scherwentke Oct 29 '14 at 13:14
• @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$. – Przemysław Scherwentke Oct 29 '14 at 13:34
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$.