What is the smallest integer $k$, for fixed $n$ (or vise versa), does $2^k! \geq 2^{n-k}$?

Question

What is the smallest integer $k$, for fixed $n$ (or vise versa), does $2^k! \geq 2^{n-k}$?

I tried to find $k$ for small $n$ so I could get some OEIS hit, but both sides just grow too fast for me to get enough values.

Any ideas?

Answer 1

This is a SKETCH. See if you can't fill in the details yourself.

Well,

$$4^{-2^k}(2^k)^{2^k} = 2^{(k-2)2^k} \ \le (2^k)! \ \le (2^k)^{2^k} = 2^{k2^k}$$

[Make sure you see why.] So from the above, we observe the following: On the one hand, $(2^k)!$ is bigger than $2^{n-k}$ if the inequality $(k-2)2^k \ge n$ is satisfied, which happens for $k \ge \log_2 n - \log_2\log_2 n+2$ for large $n$). Also from the above we observe the following: On the other hand, $(2^k)!$ is at least as large as $2^{n-k}$ only if the inequality $k2^k \ge n-k$, which will happens only if the inequality $k=\log_2 n-\log\log_2-2$ is satisfied (for large $n$).

So

$$\log_2 n -\log_2\log_2 n -2 \le k \le \log_2 n - \log_2\log_2 n + 2$$