How many positive and even factors does $2013!$ have?

Question

How many positive and even factors does $2013!$ have?

So I know that $2013 = 2\times1006 + 1$

So, does that mean $2013!$ has $1006$ even factors?

Answer 1

We list the ingredients and leave it to you to do the cooking. Let $p_0^{a_0}p_1^{a_1}\cdots p_k^{a_k}$ be the prime power factorization of $2013!$, where $p_0=2$.

Then the number of (positive) factors of $2013!$ is $(a_0+1)(a_1+1)\cdots (a_k+1)$.

The number of odd factors is $(a_1+1)(a_2+1)\cdots (a_k+1)$.

Subtract to find the answer $a_0(a_1+1)(a_2+1)\cdots(a_k+1)$ to our problem.

To find the $a_i$, note that by a standard result $$a_i=\left\lfloor\frac{2013}{p_i}\right\rfloor+ \left\lfloor\frac{2013}{p_i^2}\right\rfloor+ \left\lfloor\frac{2013}{p_i^3}\right\rfloor+ \cdots.\tag{1}$$ The computations are unpleasant, though not as bad as it might seem. A list of the primes is useful for the calculation.

For example, all the $a_i$ for $p_i\ge 1007$ are equal to $1$. Now all we need is a count of the primes between $1007$ and $2013$ to find their contribution to the answer. They contribute a multiplicative factor $2^s$, where $s$ is the number of primes in the interval.

For primes between $672$ and $1006$, the $a_i$ are equal to $2$. Things continue in a quite simple way (only one term in Formula (1)) until we get to primes $\lt\sqrt{2013}$.

Answer 2

First of all: No, 2013 has not 1006 factors. There are much more.

Think simple: How many even factors has $5!$? An even factor is one that is divisible by 2.

$5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$

The factors you're interested in are 2,4,6,8,12 (5 factors). So your system obviously doesn't work

To check a given number, you can use a simple program (Python):

def findEvenFactors(n):
    fac = 1
    for i in range(1,n+1):
        fac *= i
    counter = 0
    for i in range(2,fac,2):
        if fac % i == 0:
            counter += 1
    return counter

print(findEvenFactors(10))

12! has 719 even factors!

Answer 3

Define, for any positive integer $m$, the function$$\Lambda(m)=\begin{cases}\log p&\text{ if }m=p^k\\0&\text{ else }\end{cases}$$

Note then that if $m=p_1^{\ell_1}\cdots p_r^{\ell_r}$ we will have $$\log m=\sum_{k=1}^r\ell_k\log p_k=\sum_{d\mid m}\Lambda(d)$$

where the sum runs through all the divisors of $m$.

Reason: The $\log p_k$ entry accounts for $\Lambda(p)$ when $p$ is prime, whilst $\Lambda(p)$ will appear $\ell$ times for each divisor $p,p^2,\ldots,p^{\ell}$. On the other hand, any divisor of the form $d\cdot d'\;,\;d\neq d'$, will vanish in the right hand sum, so it will not appear on the left.

Now, suppose $m=n!$ for some $n$. We thus can write $$\log m!=\sum_{k=1}^m\log k=\sum_{k=1}^m \sum_{d\mid k}\Lambda(d)$$

Note that $$\sum_{d\mid n}f(d)=\sum_{d\geqslant 1}f(d)\left[d\mid n\right]$$

where $[P]=1$ if $P$ is true, and $0$ else. For example $$\begin{align} f(1) + f\left( 2 \right) + f\left( 4 \right) + f\left( 8 \right) &= f(1) \color{green}{\left[ {1\mid 8} \right]} + f(2)\color{green}{\left[ {2\mid 8} \right]} \cr &+\; f(3)\color{red}{\left[ {3\mid 8} \right]} + f(4)\color{green}{\left[ {4\mid 8} \right]} \cr &+\; f(5)\color{red}{\left[ {5\mid 8} \right]} + f(6)\color{red}{\left[ {6\mid 8} \right]} \cr &+\; f(7) \color{red}{\left[ {7\mid 8} \right]} + f(8)\color{green}{\left[ {8\mid 8} \right]}\\&+\;f(9)\color{blue}{\left[ {9\mid 8} \right]}+\cdots \end{align} $$

But the red terms are $0$, the green terms are $1$, and all other blue terms vanish since $[d\mid n]=0$ whenever $d>n$, so both sides coincide.

Then we can write $$\displaylines{ \sum\limits_{k = 1}^m {\sum\limits_{d\mid k} {\Lambda (d)} } = \sum\limits_{k = 1}^m {\sum\limits_{d \geqslant 1} {\Lambda (d)\left[ {d\mid k} \right]} } \cr = \sum\limits_{d \geqslant 1} {\left( {\Lambda (d)\sum\limits_{k = 1}^m {\left[ {d\mid k} \right]} } \right)} \cr} $$

where the sum extends over all numbers $d$ greater than $1$, and which by the above argument, is a actually a finite sum.

But, what is $$f(d)={\sum\limits_{k = 1}^m {\left[ {d\mid k} \right]} }\text{ ? }$$ This counts the number multiples of $d$ that do not exceed $m$. This numbers is $\left\lfloor \dfrac md\right\rfloor,$ the greatest integer preceding $\dfrac md$. Can you prove this?

Thus, we get that $$\log m! = \sum\limits_{d \geqslant 1} {\Lambda (d)\left\lfloor {\frac{m}{d}} \right\rfloor } $$

Now, the sum on the left will consist only of prime power of $p^k$ since $\Lambda$ vanishes on the others, so we can write $$\log m! = \sum\limits_\stackrel{\Large p\text{ is prime}}{{k \geqslant 1}} {\Lambda \left( {{p^k}} \right)\left\lfloor {\frac{m}{{{p^k}}}} \right\rfloor } $$ but $\Lambda\left(p^k\right)=\log p$; so $$\log m! = \sum\limits_\stackrel{\Large p\text{ is prime}}{{k \geqslant 1}} {\log p\left\lfloor {\frac{m}{{{p^k}}}} \right\rfloor } $$

This means that $$m! = \prod\limits_\stackrel{\Large p\text{ is prime}}{{k \geqslant 1}} {{p^{\left\lfloor {m/{p^k}} \right\rfloor }}} $$

This gives $m!$s prime factorization, as you can see. You can refer to Andre's answer to see how to use this to calculate what you want.

ADD To give some insight on Rob's answer. Suppose we wrote $m$ in base $p$ for a fixed prime $p$, say $$m = {\alpha _0} + {\alpha _1}p + {\alpha _2}{p^2} + \cdots + {\alpha _t}{p^t}$$ Then for each $k$; $$\frac{m}{{{p^k}}} = {\alpha _0}{p^{ - k}} + {\alpha _1}{p^{1 - k}} + {\alpha _2}{p^{2 - k}} + \cdots + {\alpha _k}{p^0} + \cdots + {\alpha _t}{p^t}$$ so that $$\left\lfloor {\frac{m}{{{p^k}}}} \right\rfloor = {\alpha _k}{p^0} + \cdots + {\alpha _t}{p^{t - k}}$$

Now summing through $k=1$ to $t$ gives $$\displaylines{ \sum\limits_{k = 1}^t {\left\lfloor {\frac{m}{{{p^k}}}} \right\rfloor } = {\alpha _1} + {\alpha _2}\left( {1 + p} \right) + {\alpha _3}\left( {1 + p + {p^2}} \right) + \cdots + {\alpha _t}\left( {1 + p + \cdots + {p^t}} \right) \cr = {\alpha _1} + {\alpha _2}\frac{{{p^2} - 1}}{{p - 1}} + {\alpha _3}\left( {\frac{{{p^3} - 1}}{{p - 1}}} \right) + \cdots + {\alpha _t}\left( {\frac{{{p^t} - 1}}{{p - 1}}} \right) \cr = {\alpha _0} - {\alpha _0} + {\alpha _1}\frac{{p - 1}}{{p - 1}} + {\alpha _2}\frac{{{p^2} - 1}}{{p - 1}} + {\alpha _3}\left( {\frac{{{p^3} - 1}}{{p - 1}}} \right) + \cdots + {\alpha _t}\left( {\frac{{{p^t} - 1}}{{p - 1}}} \right) \cr = \frac{{{\alpha _0} + {\alpha _1}p + {\alpha _2}{p^2} + {\alpha _3}{p^3} + \cdots + {\alpha _t}{p^t}}}{{p - 1}} - \left( {\frac{{{\alpha _0} + {\alpha _1} + \cdots + {\alpha _t}}}{{p - 1}}} \right) \cr = \frac{{n - {\sigma _p}\left( n \right)}}{{p - 1}} \cr} $$

as Rob has said.

Answer 4

As noted in this answer, for a prime $p$, the number of factors of $p$ in $n!$ is $$ \frac{n-\sigma_p(n)}{p-1} $$ where $\sigma_p(n)$ is the sum of the base $p$ digits for $n$. Thus, we can factor $2013!$ as

$$ 2013!=2^{2004} 3^{1002} 5^{501} 7^{333} 11^{200} 13^{165} 17^{124} 19^{110} 23^{90} 29^{71} 31^{66} 37^{55} 41^{50}\cdots $$ The number of factors of $2013!$ would be $$ (2004+1)(1002+1)(501+1)(333+1)(200+1)(165+1)(124+1)(110+1)(90+1)\cdots $$ The number of odd factors of $2013!$ would be $$ (1002+1)(501+1)(333+1)(200+1)(165+1)(124+1)(110+1)(90+1)\cdots $$ Thus, the number of even factors would be $$ 2004(1002+1)(501+1)(333+1)(200+1)(165+1)(124+1)(110+1)(90+1)\cdots $$ far more than $1006$.