Prime Powers Dividing Factorials

We will solve this for a general prime $p$ . There are 3 distinct values for $A_p(k)$ , namely $0, p-1, p$ .

Recall that for a prime $p$ and a positive integer $n$ , the number of prime powers of $p$ that divides $n !$ is

$k_p(n) = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + \lfloor \frac{n}{p^3} \rfloor + \ldots$

First, we will show that these 3 values exist.
The values of $A_p (0)$ satisfy $p^0 \mid n!$ and $p^1 \not \mid n!$ , so $n = 1, 2, \ldots, p-1$ . There are $p-1$ of them.
The values of $A_p (1)$ satisfy $p^1 \mid n!$ and $p^2 \not \mid n!$ , so $n = p, p+1, \ldots, 2p-1$ . There are $p$ of them.
The values of $A_p (p)$ satisfy $p^p \mid n!$ and $p^{p+1} \not \mid n!$ . We know that $n < p^2$ is not sufficient, since $k_p ( p^2 - 1) = p-1$ . However, $k_p(p^2 ) = p+1$ . This means that if $p^p \mid n!$ , then $p^{p+1} \mid n!$ . Thus, there are 0 of them.

Now, we show that that's all there is. We make the following observations:

1. Claim: If $mp \leq n < (m+1) p$ for some $m \geq 1$ , then $k_p (n) = k_p (mp)$ .
   This follows because $\lfloor \frac{n}{p^i} \rfloor = \lfloor \frac{mp}{p^i} \rfloor$ for all $i$ , so their sums are the same.

2. In the case of $m = 0$ , meaning $0 < n < p$ , then we have $p-1$ positive integers in $A_p(0)$ . Henceforth, let $m \geq 1$ .

3. Since $k_p (mp) = k_p (mp+1) = \ldots = k_p (mp+p-1 )$ , this implies that $A_p (k)$ must be a multiple of $p$ . Henceforth, we can simply consider the values of $k_p (mp)$ . For each $p^k \mid (mp)!$ and $p^{k+1} \not \mid (mp)!$ , then there are $p$ values in $A_p (k)$ .

4. Claim: $k_p (mp)$ is an increasing function in $m$ .
   This is true because the floor function is an increasing function, and $\lfloor \frac{(m+1)p}{p} \rfloor \geq \lfloor \frac{mp}{p} \rfloor + \lfloor \frac{p}{p} \rfloor = \lfloor \frac{mp}{p} \rfloor + 1 > \lfloor \frac{mp}{p} \rfloor.$

5. Since $k_p(mp)$ is an increasing function, this means that there is at most 1 value of $mp$ that satisfies $p^k \mid (mp)!$ and $p^{k+1} \not \mid (mp)!$ . Hence, by observation 3, $A_p (k) = 0$ or $p$ for $k \geq 1$ .

6. In conclusion, we have $A_p (k) \in \{ 0, p-1, p \}$ .

7. The first paragraph tells us that $\{ 0, p-1, p \} \subset \{ A_p (k) \}$ . Hence, $\{ A_p (k) \} = \{ 0, p-1, p \}$ .

This establishes that the answer is at most 3.

There are $3$ distinct values of $A_p(k)$ , for any prime $p$ . The distinct values are: $0, p-1$ and $p$ .

Let's first see when $A_p(k)$ can be $0$ .

Consider the integers $n=x \times p^m$ for some integers $m>1$ and $x\geq 1$ , with $p \not \mid x$ . Also assume that $a\geq 0$ is the highest exponent of $p$ such that $p^a \mid (n-1)!$ . Then $n!$ is simultaneously the FIRST factorial that is divided by $p^{a+1}, p^{a+2},\ldots{ } \ldots{ } \ldots{ }$ and $p^{a+m}$ . Now, it is easy to see that $A_p(k)=0$ for $k=a+1, a+2,\ldots{ } \ldots{ } \ldots{ }$ and $a+m-1$ .

Now how $A_p(k)$ can be $p$ ?

Recall the argument for [When $A_p(k)$ can be $0$ ]. It's obvious that $p^k \mid n!$ but $p^{k+1} \not \mid n!$ for $k=a+m$ . Notice that the next multiple of $p$ after $n=x \times p^m$ is $n+p=x \times p^m+p$ . As the number of integers $w$ such that $n\leq w \leq (n+p-1)$ is $p$ and for each $w$ , $p^{a+m} \mid w!$ but $p^{a+m+1} \not \mid w!$ , and $p^{a+m} \not \mid (n-1)!$ , and $p^{a+m+1} \mid (n+p)!$ , then $A_p(k)=p$ for $k=a+m$ .

I believe it's already clear that $A_p(k)$ can't exceed $p$ .

Then when $A_p(k)$ can be $(p-1)$ ?

Consider the case when $k=0$ . Then we have $n=1, 2,\ldots{ } \ldots{ } \ldots{ },(p-1)$ such that $p^k=p^0=1 \mid n!$ but $p^{0+1}=p^1 \not \mid n!$ , and $p^{0+1}=p^1 \mid p!$ . So, $A_p(0)=(p-1)-1+1=p-1$ . Why not $n=0$ ? Notice, in the problem statement, $n$ is one of the positive integers (excluding 0), and this effect of $n$ being a positive integer on the value of $A_p(0)$ is chosen by design. Of course, if you change the domain of $n$ to the set of non-negative integers, then the value of $A_p(k)$ will be $p$ for $k=0$ . Then their would be only $\boxed{2}$ distinct values of $A_p(k)$ .

We are just one-step behind to Completeness , which we can arrive in just by proving the fact that:

$A_p(k)$ is either $0$ or $p$ for $k\geq1$ .

Let's prove it.

From the argument for [When $A_p(k)$ can be $0$ ], we can see, $A_p(k)$ can be $0$ for $k\geq1$ , since each of (a+1), (a+2), $\ldots{ } \ldots{ } \ldots{ }$ and $a+m-1$ is greater than $1$ (as $a\geq0$ . Now it'll suffice to show that: For $k\geq1$ , $A_p(k) \neq 0 \implies A_p(k)=p$ .

If $A_p(k) \neq 0$ implies there is a positive integer $n$ such that $p^k \mid n!$ but $p^{k+1} \not \mid n!$ . Now there arises two distinct cases.

• CASE-I: $n$ is a multiple of $p$ : Then $p^k \not \mid (n-1)!$ . But for each $w$ , with $n\leq w \leq (n+p-1)$ , $p^k \mid w!$ but $p^{k+1} \not \mid w!$ , and $p^{k+1} \mid (n+p)!$ . So, $A_p(k)=(n+p-1)-n+1=p$ .

• CASE-II: $n$ is NOT a multiple of $p$ :Then

$p^k \mid (n-1)!$ . If $n-1$ is a multiple of $p$ , then the argument is reduced to CASE-I. If not, then

$p^k \mid (n-2)!$ . If $n-2$ is a multiple of $p$ , then the argument is reduced to CASE-I. If not, then

$\ldots{ } \ldots{ } \ldots{ }$

$\ldots{ } \ldots{ } \ldots{ }$

$\ldots{ } \ldots{ } \ldots{ }$

$p^k \mid (n-x)!$ ; now $(n-x)$ is a multiple of $p$ , then the argument is reduced to CASE-I. As $n\geq p$ whenever $p^k \mid n!$ but $p^{k+1} \not \mid n!$ for $k \geq 1$ , and for any prime $p$ and any positive integer $n$ , there is an $x$ , with $0\leq x<p$ , such that $(n-x)$ is multiple of $p$ , we can be sure that $(n-x)$ is a positive integer and thus, the factorial is defined.

That completes the proof:

There are $\boxed{3}$ distinct values of $A_p(k)$ , for any prime $p$ . The distinct values are: $0, p-1$ and $p$ .

So, $\boxed{|A_{2017}|=3}$ .