Find the largest $k$ such that $3^k$ divides the product of the first $100$ odd integers

Let $P$ be the product of the first 100 positive odd integers. Find the largest integer $k$ such that $P$ is divisible by $3^k$.

There are $50$ odd numbers and $50$ even numbers between $0$ and $100$, $99$ being the $50$th odd. So it makes sense that, $199$ is the $100$th odd number.

I got that $$P = 1 \cdot 3 \cdots 199 = \frac{200!}{2 \cdot 4 \cdot 6 \cdots 198},$$

but that doesn't really help.

I am after $$\prod_{n = 0}^{99} (2n + 1),$$ but I don't see a general formula.

You may notice that $$P=\frac{200!}{2^{100}\cdot 100!}$$ Now use that a prime $p$ occurs in $n!$ with multiplicity exactly $$\lfloor n/p\rfloor + \lfloor n/p^2\rfloor + \lfloor n/p^3\rfloor + \lfloor n/p^4\rfloor +\ldots$$

• So we find factors of $3$ in the numerator? How do you know that a prime $p$ occurs in $n!$ with multiplicity: $[n/p] + [n/p^2] + ...$? Also what about the denominator? – Lebes Apr 14 '15 at 14:58

How many integers less than $199$ does $3$ divide? Every second of those are odd, starting with $3,9,15,...$

How many integers less than $199$ does $3^2$ divide? Every second of those are odd, starting with $9,27,45,...$ Note that all of those were already divisible by $3$ so already counted once before.

Combine those informations (add up all those figures) up to $3^4$, since $3^5=243>199$. I get $k=33+11+4+1=49$.

This figure is confirmed by Wolfram|Alpha.

• @Travis: Thank you - I did not notice that "slip of my finger". – String Apr 14 '15 at 13:47
• Cheers, glad to help. – Travis Apr 14 '15 at 13:47
• @Travis: Ah, stupid me! Clever you ;) – String Apr 14 '15 at 13:52
• But aren't you overcounting the $9$ for example? – Lebes Apr 14 '15 at 13:57
• @Lebes: Regarding $9$, $3$ divides it twice, and it is counted twice. Firstly as a number divisible by $3$, secondly as a number divisible by $9$. And it is then never counted again, since it is not divisible by $27$ etc. – String Apr 14 '15 at 13:59

evidently the highest power of $3$ dividing the first $100$ odd numbers is the same as the highest power of $3$ which divides $\frac{200!}{100!}$

$$200 = 2.3^4 +1.3^3 + 1.3^2+ 0.3^1+2.3^0$$ so the sum-of-digits in the 3-ary represention of 200 is 6. similarly for 100 the sum of 3-ary digits is 4.

hence the number required is: $$\frac{200-6}{3-1} - \frac{100-4}{3-1} = 97-48 = 49$$