Designate set $ \lbrace n \in\mathbb N : 2^{n-1} | n! \rbrace $

Question

Actually I found out that if $n = 2^k$, $k\in\mathbb Z_{+}$ we can say that it's true.

Here's the proof:

Let $n = 2^k$, $k\in\mathbb Z_{+}$ Then $\nu _{2}(n!) = \nu _{2}((2^k)!) = \lfloor \frac{2^k}{2} \rfloor + \lfloor \frac{2^k}{4} \rfloor +\dots+ \lfloor \frac{2^k}{2^p} \rfloor $ where $2^p \leq n < 2^{p+1}$.

Further we have: $\nu _{2}(n!) = 2^{k-1} + 2^{k-2} +\dots+2+1 = 2^k - 1$ and $ \nu _{2}(2^{n-1}) = 2^k - 1 $. Since $\nu _{2}(2^{n-1}) \leq \nu _{2}(n!) $ we can say that $\nu _{p}(2^{n-1}) \leq \nu _{p}(n!) $ and this part implies that $2^{n-1} \mid n!$.

My problem is that I can't prove it's false for numbers $n = 2^k*a $ where $a$ is a non-negative odd number and $a > 1$.

Answer 1

The power of $2$ in $n$ is given by $\left\lfloor\frac n2\right\rfloor+\left\lfloor\frac n4\right\rfloor+\cdots\left\lfloor\frac n{2^{p}}\right\rfloor$ where $2^p\leq n<2^{p+1}$

For the given condition to be satisfied, we have

$$n-1\leq \left\lfloor\frac n2\right\rfloor+\left\lfloor\frac n4\right\rfloor+\cdots+\left\lfloor\frac n{2^{p}}\right\rfloor$$

$$\left\lfloor\frac n2\right\rfloor+\left\lfloor\frac n4\right\rfloor+\cdots+\left\lfloor\frac n{2^{p}}\right\rfloor\leq\frac n2+\frac n4+\cdots+\frac n{2^p}=n-\frac{n}{2^p}$$

However, as $n\geq2^p$, $$n-\frac{n}{2^p}\leq n-1$$

As equality must be satisfied everywhere, we have that $\frac n{2^k}$ is an integer for $1\leq k\leq p$, that is, $n=2^p$.

Answer 2

You can also use Legendre's formula directly which is,

$$v_p(n!) = \frac{n-s_p(n)}{p-1},$$

$s_p(n)$ being the sum of digits of $n$ when written in base $p$.

The condition $2^{n-1} \mid n!$ is equivalent to $v_2(2^{n-1}) \le v_2(n!)$, thus

$$n-1 \le \frac{n-s_2(n)}{2-1}.$$

This simplifies to, $$s_2(n) \le 1.$$

The only numbers in base 2 with one digit are powers of 2, furthermore if you consider 0 a natural number then you also have 0.