Powerful Factorial

There were lots of interesting patterns that could be identified and explained in this problem. Ngoc from Nguyen Truong To junior high school (Vietnam) identified some interesting patterns along with giving the answers. Well done Ngoc. It is also good, once you have identified patterns, to try to explain them in terms of the mathematics they came from. So where do the patterns Ngoc and Andrei (School 205, Bucharest) come from?

Ngoc's contribution:

The highest power of 2 that divides exactly to 100! is 97
The highest power of 3 that divides exactly to 100! is 48

General form:

with all n, k are positive integers, n > k
The highest power of k (called y) that divides exactly to n! is:

y = n/k + n/k ² + n/k ³ + ... + n/k ^z
with n/k, n/k ² ... are nearest integers, and z < = n

Andrei's Contribution

I started working with 100!.

• I observe that the greatest number - power of 2 that is smaller than 100 is 2 ⁶ . It enters 100 only once.
• Now, I consider the consecutive power of 2 smaller than 2 ⁶ (2 ⁵ ). This number enters in 100 3 times. However, it is clear that 2 ⁶ is divisible with 2 ⁵ . Therefore, I take this number (3 - 1 =) 2 times.
• Now, I take 2 ⁴ . It enters in 100 6 times. However, three of the six combinations is also a multiple of 32 (including 64).So, I take this number (6 - 3 =) 3 times.
• It is now the turn of 2 ³ . It enters in 100 12 times. However, here it is also the case that six were also multiples of 16. So, there remain only six combinations.
• The case of 2 ² is similar it enters in 100 25 times, but there remain only 13 combinations.
• Finally, two. It enters in 100 50 times, but I use only 25 of them.

To calculate the total highest power of two that divides exactly into 100! is calculating by multiplying the corresponding power of two with the number of solutions and multiplying the results, because it is 100!:

(2 ⁶ ) ¹ * (2 ⁵ ) ² * (2 ⁴ ) ³ * (2 ³ ) ⁶ * (2 ² ) ¹³ * (2 ¹ ) ²⁵ = 2 ⁶ * 2 ¹⁰ * 2 ¹² * 2 ¹⁸ * 2 ²⁶ * 2 ²⁵ = 2 ⁹⁷

I use the same method for dividing 100! into powers of three:

Power of 3	3n < 100!	Combinations	Result
3 4	1	1	1
3 3	3	3 - 1	2
3 2	11	11 - 3	8
3	33	33 - 11	2

Here the greatest power of three that divides exactly into 100!:

(3 ⁴ ) ¹ * (3 ³ ) ² * (3 ² ) ⁸ * (3 ¹ ) ²² = 3 ⁴ * 3 ⁶ * 3 ¹⁶ * 3 ²² = 3 ⁴⁸

Now, the general method with n! as the number, and x as the number whose powers enter n!:

• Calculate the greatest power of x ^k that is smaller than n and observe how many times it enters n. Note the result with a.
• Calculate how many times x ^k-1 enters n. Then subtract the precedent result (before subtracting something). Note the result with b.
• Continue this method up to x ¹ .
• Now, calculate the greatest power of x that divides exactly into n: (x ^k ) ^a * (x ^k-1 ) ^b * (x ^k-2 ) ^c * ... * (x ¹ ) ^z
  

I would like to mention that I used for 100! and for the powers of 2 the traditional method, it means 100 is divisible by 2 ² , 98 by 2, ? and so on, and I obtained the same result as before.