Factorial problem

Were you shown an interesting trick or shall we just count them?

37 - Nope. No factor of 3, there.
36 - 6*6 = 4*9 -- There's two 3s.
35
34
33 -- There's one. That's 3 total
32
31
30 -- One more. Only 4, still
29
28
27 - Aha! 3 more. We're up to 7
26 - Nope.

Now the denominator.

12 - There's 1 (down to 6)
11
10
9 - Two more - Down to 4
8
7
6 - Hit one - Down to 3
5
4
3 - Last one. Down to 2
2
1 - Nope.

Looks like 3^2

For larger numbers, you'll need a better plan. In this case, it's not hard to see that we get 3s from every third value. Some generalization will get us there.
 
Hello, 1a2s3d4f5g6h7j8k9l!

\(\displaystyle \text{Find the largest power of 3 that divides: }\:\dfrac{37!}{25!\,12!}\)

\(\displaystyle [x]\) is the "greatest integer function".



\(\displaystyle \text{Factors of 3 in 37! }\;\;\left[\frac{37}{3}\right] + \left[\frac{37}{3^2}\right] + \left[\frac{37}{3^3}\right] \;=\;12 + 4 + 1 \;=\;17\)

\(\displaystyle \text{Factors of 3 in 25! }\;\;\left[\frac{25}{3}\right] + \left[\frac{25}{3^2}\right] \;=\;8+2\;=\;10\)

\(\displaystyle \text{Factors of 3 in 12! }\;\;\left[\frac{12}{3}\right] + \left[\frac{12}{3^2}\right] \;=\;4 + 1 \;=\;5\)


The numerator is of the form: .\(\displaystyle a\cdot3^{17}\)

The denominator is of the form: .\(\displaystyle (b\cdot3^{10})(c\cdot 3^5)} \:=\:bc\cdot 3^{15} \)


Hence: .\(\displaystyle \dfrac{37!}{25!\,12!} \;=\;\dfrac{a\cdot3^{17}}{bc\cdot3^{15}} \;=\;\dfrac{a}{bc}\cdot 3^2\)


The highest power of 3 is 2.
 
Hello, everyone!


In case, you didn't understand the technique I used . . .


Note: \(\displaystyle [x]\) is the "greatest integer function".


How many factors-of-3 are contained in 37-factorial?

We know that: .\(\displaystyle 37! \;=\;1\cdot2\cdot3\cdot4\cdots 37 \)


We know that every third number has a factor of 3.
. . There are: .\(\displaystyle \left[\frac{37}{3}\right] \:=\: 12\) factors-of-3.


But every ninth number has \(\displaystyle 3^2\),
. . each of which contributes another factor-of-3.
There are: .\(\displaystyle \left[\frac{37}{9}\right] \:=\: 4\) more factors-of-3.


And every twenty-seventh number has \(\displaystyle 3^3\),
. . each of which contribute yet another factor-of-3.
There is: .\(\displaystyle \left[\frac{37}{27}\right] \:=\:1\) more factor-of-3.


Therefore, \(\displaystyle 37!\) contains: .\(\displaystyle 12 + 4 + 1 \:=\:17\) factors-of-3.
 
Top