VWO Problem 2 2016

The prime factor $p^q$ of a factorial $r!$ is given by $q = \displaystyle \sum_{k=1}^\infty \left \lfloor \dfrac r{p^k} \right \rfloor$ . The smallest $n$ such that $n^n$ does not divide $2016!$ is therefore the smallest prime $p$ with $q < p$ . Then $q < \left \lfloor \dfrac rp \right \rfloor$ . Since $p \approx q$ , we have $q^2 \approx r = 2016$ , $\implies q \approx \sqrt{2016} \approx 44.90$ . This means that $p > q$ is the smallest prime greater than 44.90, which is 47. We note that $q < \left \lfloor \dfrac {2016}{47} \right \rfloor = 41$ . This means that $47^{41} \mid 2016!$ but for any $q > 41$ , $47^q \nmid 2016!$ and $47^{47} \nmid 2016!$ . Therefore $n=p=\boxed{47}$ .

Clearly, n should be a prime (try to see why). Knowing that 2016 is about 2025 = 45², we will look at some primes that are close to 45. However, 43 does not work since 43² < 2016 such that 2016! contains at least 43 factors of 43 and therefore, 43^43 divides 2016!. Now, we look at the smallest prime that is greater than 43, which happens to be 47. Since 47² = 2209 > 2016, it is plain that 2016! cannot contain the factor 47 at least 47 times. Hence, 47^47 does not divide 2016! and it is also teh smallest positive integer with this property.

I wrote a Python program that worked out the answer.

1
2
3
4
5
6

import math,sys
a=math.factorial(2016) #2016!
for i in range(2016):
    if a%(i**i)!=0: #If it's not divisible
        print(i) #Print the answer
        sys.exit() #End of the program

Output:

1

47