Can $n!$ be expressed as the sum of $n$ powers of 2?

Solution 1:

As stated by others, the number of 1 bits in $n!$ exceeds $n$ for $n=10, 15, 16, 17, 18, 20 $ and, seemingly, all larger $n$.

Here is a heuristic estimate,

$n!$ has about $\dfrac{n(\ln(n)-1)}{\ln(2)} $ bits. Of these, about the last $n$ bits are $0$'s, which leaves $\dfrac{n(\ln(n)-1)}{\ln(2)}-n =\dfrac{n(\ln(n)-1-\ln(2))}{\ln(2)} $.

If these are equally $0$ and $1$, about half of these should be $1$, which is $ \dfrac{n(\ln(n)-1-\ln(2))}{2\ln(2)} $. This exceeds $n$ by $ \dfrac{n(\ln(n)-1-\ln(2))}{2\ln(2)}-n =\dfrac{n\ln(n/(8e))}{2\ln(2)} $ which is positive for $n \ge 24$.

This agrees moderately well with computations. Dividing the actual number of bits minus $n$ by this gives this result for $n$ from $20$ to $100$:

-1.65608, -7.56194, 32.5906, 8.60243, 2.92876, 1.98846, 2.68602, 2.60998, 2.74228, 1.82674, 2.58512, 1.38744, 1.12147, 1.30942, 1.55095, 1.74777, 1.1459, 1.48043, 1.3726, 1.52135, 1.30796, 1.33301, 1.1032, 1.32408, 1.34119, 1.05905, 1.24699, 1.30121, 1.49556, 1.32338, 1.29874, 1.2437, 1.10087, 1.20381, 0.931435, 1.19522, 1.23003, 1.03482, 1.04767, 1.17707, 1.20658, 0.92541, 1.08843, 1.17916, 1.12374, 0.857042, 1.0784, 0.992945, 1.10869, 0.904802, 1.135, 1.13861, 1.17401, 1.16042, 1.19321, 1.0003, 0.99127, 1.18187, 1.08536, 1.26508, 1.03766, 1.19737, 1.19731, 1.19712, 1.09911, 0.801583, 1.07863, 0.999876, 0.946624, 0.917429, 1.16037, 1.09619, 1.14919, 1.1694, 1.24926, 0.979809, 0.982215, 1.16607, 1.18389, 0.979308, 0.972214

This seems to be around $1$.

Note: I used Mathematica's DigitCount function for the computations.

Solution 2:

The statement holds trivially for n=0,1.

Note that all even numbers can be written as $2^p(q)$ where q is odd.

Since n! is an even number for $n\ge2$,

Factor $n!=2^p(q)$ where q is odd.

Since q is odd, $q= q^{'} + 1$ where $q^{'}$ is even.

$$ \implies n! = 2^p(q) = 2^p(q^{'} + 1) = 2^p + 2^pq^{'}$$

Now since $2^pq^{'}$ is even, the same factorisation can be repeated until the remnant is of the form $2^p.1$

Edit: Just realised that the question is asking to prove that it is the sum of n such powers of 2. Still leaving this answer in case this helps somebody figure out a different approach.