3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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 $$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Lebes Apr 14 '15 at 14:58
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Travis: Thank you - I did not notice that "slip of my finger". $\endgroup$ – String Apr 14 '15 at 13:47
  • $\begingroup$ Cheers, glad to help. $\endgroup$ – Travis Apr 14 '15 at 13:47
  • $\begingroup$ @Travis: Ah, stupid me! Clever you ;) $\endgroup$ – String Apr 14 '15 at 13:52
  • $\begingroup$ But aren't you overcounting the $9$ for example? $\endgroup$ – Lebes Apr 14 '15 at 13:57
  • $\begingroup$ @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. $\endgroup$ – String Apr 14 '15 at 13:59
0
$\begingroup$

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 $$

$\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.