n! is really even

The maximum power of 2 which divides $n!$ is given by:

$S(n) := \left[ \frac n 2\right] + \left[ \frac n 4\right] + \left[ \frac n 8\right] + \ldots$

First note that $S(n) \le n-1$ since the infinite sequence $\frac n 2 + \frac n 4 + \frac n 8 + \ldots$ equals $n$ and so $S(n) \le n$ ; but equality cannot hold since that would require $\left[\frac n {2^k}\right] = \frac n{2^k}$ for all $k$ , which is impossible for positive $n$ . Since $S(n)$ is an integer, we must have $S(n) \le n-1$ .

Next, $\left[\frac 1 j \left[ \frac n k\right]\right] = \left[ \frac n {jk} \right]$ for positive integers $n, j, k$ , so:

$S(n) = \left[ \frac n 2\right] + S( [n/2] ).$

We say that a positive integer $n$ is brilliant if $S(n) = n-1$ .

Claim 1 : $n=1$ is brilliant.

Claim 2 : if $n>1$ is odd, then it's not brilliant.

Proof : Write $n = 2j-1$ for an integer $j \ge 1$ . Then $\left[ \frac n 2\right] = j-1$ so we have $S(n) = j-1 + S(j-1) \le j-1 + (j-2) = 2j-3 < n-1$

and the result follows.

Claim 3 : $n=2k$ is brilliant if and only if $k$ is brilliant.

Proof : Again, since $\left[\frac n 2\right] = k$ we have $S(n) = k + S(k)$ , so $S(n) = n-1$ holds if and only if $S(k) = k-1$ , so the result follows.

From the above claims, $n$ is brilliant if and only if it's a power of 2.

We can see that if $n = 2^k$ for some positive integer $k$ and the function $\pi_2(n)$ giving the number of prime factors 2 in $n$ , we have: $\pi_2(2^k!) = 2^{k-1} + \pi_2(2^{k-1}!) \Rightarrow \pi_2(2^k!) = 2^k-1$ And hence, $\pi_2(n!) = n - 1 \Rightarrow 2^{n-1} | n!$

Otherwise, having $n = 2^k+m$ with $0<m<2^k$ , we have: $\pi_2((2^k+m)!) = \pi_2(2^k!) + \pi_2(m!) \Rightarrow$ $\pi_2(n) = 2^k-1+\pi_2(m) = \pi_2(m!) + n-m-1$

We must investigate if $\pi_2(n!) \geq n-1$ , but from last result we have: $\pi_2(n!) = \pi(m!)+n-m-1 \geq n-1 \Rightarrow \pi_2(m!) \geq m$

And that's impossible, because obviously $n = 2^k$ is the best case possible and $\pi_2(n!) < n$ .

So, the only solutions are $n = 2^k$ , $k \in \{0,1,...,9\}$

We claim that $2^{n-1}|n!$ if and only if $n$ is a power of $2$ .

First, recall by Legendre's Theorem that the largest power of $2$ that divides $n!$ is $f(n)=\left\lfloor \frac{n}{2}\right \rfloor+\left\lfloor \frac{n}{2^2}\right\rfloor+\left\lfloor \frac{n}{2^3}\right\rfloor+\cdots$ (Call it $f(n)$ for convenience.) Thus, the claim is equivalent to showing that $f(n)\ge n-1$ if and only if $n$ is a power of $2$ . In fact, we will prove the stronger statement:

Lemma: $f(n)=n-1$ if $n$ is a power of $2$ and $f(n)<n-1$ otherwise.

Proof: If $n$ is a power of $2$ , then we can write $n=2^m$ for some nonnegative integer $m$ , and $f(n)=2^{m-1}+2^{m-2}+\cdots+1=2^m-1= n-1$ as expected.

Now we use induction to prove that if $n$ is not a power of $2$ , then $f(n)<n-1$ . We will prove that for all positive integers $m\ge 2$ , every positive integer $n$ less than $2^m$ that is not a power of $2$ satisfies $f(n)<n-1$ . The base case $m=2$ is trivial since $f(3)=1<3-1$ . Now assume the statement holds for some $m=k$ . To prove that it is true for $m=k+1$ we need to show that for all $2^k<n<2^{k+1}$ that are not powers of $2$ , $f(n)<n-1$ . Note that $n$ can be written as $n=2^k+a$ for some $0<a<2^k$ . Thus $\begin{aligned} f(n)=f(2^k+a)&=&2^{k-1}+\left\lfloor \frac {a}{2}\right \rfloor+2^{k-2}+\left \lfloor \frac{a}{2^2}\right \rfloor+\cdots \\ &=& 2^{k-1}+2^{k-2}+\cdots+1+f(a)\\ &=&2^k-1+f(a)\\ &\le& 2^k-1+(a-1)\\ &=&2^k+a-2\\ &<&2^k+a-1 \end{aligned}$ which completes the induction. $\square$

Thus the claim at the beginning is proved and it only remains to compute the number of powers of $2$ less than $1000$ . Since $2^9<1000<2^{10}$ , the answer is $9+1=\boxed{10}$ .

My way is listing the disibility of n! By 2^(n-1) from n=1 until I found the pattern

List => n=1 -> 1|1 => n=2 -> 2|2 => n=3 -> not => n=4 -> 8|24 => n=5 -> not . . . . => n=8 -> 128|40320 => n=9 -> not => n=10 -> not

From this list , we not for every n which can be formed as 2^k , with k positve integers , 2^(n-1) divide n! So n=2^0 , 2^1 , 2^2 , ... , 2^9 ->> We get 10 solutions

The highest power of 2 that divides $n!$ is $\lfloor{\frac{n}{2}\rfloor}+\lfloor{\frac{n}{4}\rfloor}+\cdots.$ Note that this is less than $\frac{n}{2}+\frac{n}{4}+\cdots=n.$ One can probably guess that $\lfloor{\frac{n}{2}\rfloor}+\lfloor{\frac{n}{4}\rfloor}+\cdots=n-1$ when $n$ is a power of two. Indeed, $\lfloor{\frac{2^k}{2}\rfloor}+\lfloor{\frac{2^k}{4}\rfloor}+\cdots=2^{k-1}+2^{k-2}+\cdots+1=2^k-1.$ If $n$ is not a power of two, then we have $2^{k}<n<2^{k+1}$ for some integer $k$ . But then $\lfloor{\frac{n}{2^k}\rfloor}=0$ and thus $\lfloor{\frac{n}{2}\rfloor}+\lfloor{\frac{n}{4}\rfloor}+\cdots+\lfloor{\frac{n}{2^k}\rfloor} \le \frac{n}{2}+\frac{n}{4}+\cdots+\frac{n}{2^{k-1}}+0$ $=\frac{(2^{k-1}-1)n}{2^{k-1}}$ $<n-1,$ a contradiction. Thus, only $n=1,2,...,512$ work, so there are 10 solutions.

if we try for the first few numbers, we find that every number that can be expressed as 2 power n satisfies the equation( 2^0=1;2^1=2;2^2=4.......2^9=512) therefore 10 numbers

It can be divided as long as the degree of 2 in n! is greater than or equal to (n-1). This condition is fulfilled when n is one of the power of 2. Every time n=2^a, flooring (2^a/2) gives ((2^a)-1)) which is (n-1). So total there are 9 possibilities from this method (2, 4, 8, 16, 32, 64, 128, 256, 512), and including the fact that n=1 (2^0) is also an answer, there are total 10 possibilities.

1,2,4,16,32,64,128,256,512 the logic is double of the number satidfies the condition