Factorial factors

First of all, let us see how many factors does any number $n$ have.

If $n=p_1^{i_1}p_2^{i_2}\cdots p_k^{i_k}$ where $p_1,p_2,\cdots,p_k$ are the distinct prime factors of $n$ ; then number of factors of $n$ would be

Then any factor of $n$ would be of the form $m=p_1^{q_1}p_2^{q_2}\cdots p_k^{q_k}$ with $0 \leq q_j \leq i_k, \forall j=1 \cdots k$

Thus the number of distinct factors of $n$ would be

$N(n)=\displaystyle\prod_{j=1}^k (i_j+1)$ .

Hence,

$N_p(n)=\displaystyle\left(\prod_{j=1}^k (i_j+1)\right)$ ...... (Eq. 1)

with each prime $p_j$ factor being considered 0 to $i_j$ times.

Now, the part to do the prime factorization of $n!$ .

If there are $k$ prime numbers lesser than or equal to $n$ , then $n!$ would have those $k$ primes in its prime factorization.

$n!=2^{r_1}3^{r_2}\cdots p_k^{r_k}$

The radix $r_j$ is the number of times the prime number $p_j$ appears in $n!$ . This can be easily calculated as

$r_j = \left[\frac{n}{p_j}\right]+\left[\frac{n}{p_{j}^{2}}\right]+\left[\frac{n}{p_{j}^{3}}\right]+\cdots$

From this we can determine that

$20! = 2^{(10+5+2+1)}3^{(6+2)}5^{4}7^{2}11^{1}13^{1}17^{1}19^{1}$

$20!=2^{18}3^{8}5^{4}7^{2}11^{1}13^{1}17^{1}19^{1}$

$N_p(20!) = 19\times 9\times 5\times 3 \times 2 \times 2 \times 2 \times 2 = 41040$

and

$21! = 2^{(10+5+2+1)}3^{(7+2)}5^{4}7^{3}11^{1}13^{1}17^{1}19^{1}$

$21! = 2^{18}3^{9}5^{4}7^{3}11^{1}13^{1}17^{1}19^{1}$

$N_p(21!) = 19\times 10\times 5\times 4 \times 2 \times 2 \times 2 \times 2= 60800$

Further, since $21!=21\times 20!$ , each factor of $20!$ is also a factor of $21!$ .

So, the required solution would be

$N_p(21!)-N_p(20!) = 60800-41040 = \boxed{19760}$

Our instincts tell us that factorizing $21!$ and $20!$ would be useful. So, with a bit of scratch work, we can see that $20! = 2^{18}\cdot3^{8}\cdot5^4\cdot7^2\cdot11\cdot13\cdot17\cdot19$ $21! = 2^{18}\cdot3^{9}\cdot5^4\cdot7^3\cdot11\cdot13\cdot17\cdot19$ $21!/20! = 3\cdot7$ It's evident that $21!$ brings an extra $3$ and $7$ along with it, so, we can conclude that the proper divisors of $21!$ that do not properly divide $20!$ have one or both of those extra factors. More specifically, our desired divisors $d$ must be in one of the following three forms: $d_1 = 2^a\cdot3^9\cdot5^b\cdot7^3\cdot11^c\cdot13^d\cdot17^e\cdot19^f$ $d_2 = 2^a\cdot3^x\cdot5^b\cdot7^3\cdot11^c\cdot13^d\cdot17^e\cdot19^f$ $d_3 = 2^a\cdot3^9\cdot5^b\cdot7^y\cdot11^c\cdot13^d\cdot17^e\cdot19^f$

where we have non-negative integers $a, b, c, d, e, f, x, y$ in the following intervals:
$a\in[0,18]$ $b\in[0,4]$ $c, d, e, f\in[0,1]$ $x\in[0,8]$ $y\in[0,2]$

Now, for the case of $d_1$ , we can see that there are $19\cdot5\cdot2\cdot2\cdot2\cdot2 = 1520$ such divisors.

In similar suit for $d_2$ , we can see there are $19\cdot9\cdot5\cdot2\cdot2\cdot2\cdot2 = 13680$ such divisors.

And finally, for $d_3$ , there are $19\cdot3\cdot5\cdot2\cdot2\cdot2\cdot2 = 4560$ such divisors.

All that's left is to sum them up, giving us $1520+13680+4560 = \boxed{19760}$

The main trick is to find the number of proper factors of 21! That is 60798. Similarly the number of proper factors of 20! Is 41038 Then subtract them to get the answer.

It is well-known that the highest power of p that divide n! is f(n, p) = floor(n/p)+floor(n/p^2)+floor(n/p^3)+.... So

f(20, 2) = 10+5+2+1 = 18,

f(20, 3) = 6+2 = 8,

f(20, 5) = 4,

f(20, 7) = 2,

f(20, 11) = f(20, 13), f(20, 17), f(20, 19) = 1.

Therefore 20! = (2^18)(3^8)(5^4)(7^2) * 11 * 13 * 17 * 19, and since 21! = 20! * 3 * 7, so 21! = (2^18)(3^9)(5^4)(7^3) * 11 * 13 * 17 * 19. It is also well-known that the number of factors of n with prime-factorization n = (p^a)(q^b)(r^c) * ... is g(n) = (a+1)(b+1)(c+1) * .... Therefore the number of proper factors of 21! that are not proper factors of 20! is

[g(21)-2]-[g(20)-2]

= g(21)-g(20)

= (18+1)(4+1)(1+1)^4 * [(9+1)(3+1)-(8+1)(2+1)]

= 19760,

where we subtracted 2 from both g(21) and g(20) above to remove the improper factors.