Existe un n tal que $2^n|n!$?

Question

Si existe un $n$ $n$ debe ser el más alto de potencia de 2 que divide a $n!$. Pero para encontrar el mayor poder que necesitamos para aumentar n para cada paso hasta que llegue a $n$. Alguna idea?

Gracias,
Chan

Answer 1

La potencia de 2 que divide a n! es $\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor +\lfloor \frac{n}{8} \rfloor + \ldots \lfloor \frac{n}{2^k} \rfloor$ Esto nunca puede ser más de $n-1$, que se produce cuando $n$ es una potencia de 2.

Answer 2

No. Considere la fórmula debido a Legendre: el poder de la prime $p$ en la factorización de $n!$$\sum_{k=1}^\infty \lfloor n/p^k \rfloor$. En el caso de $p=2$$\sum_{k=1}^\infty \lfloor n/2^k \rfloor$. Pero

$$ \sum_{k=1}^\infty \lfloor n/2^k \rfloor < \sum_{k=1}^\infty n/2^k $$

ya que no podemos tener $n/2^k$ un entero para todos los $k$ simultáneamente, de modo que al menos uno de los términos en el lado izquierdo de la suma es menor que el correspondiente término en la mano derecha de la suma. Y la mano derecha de la suma es sólo $n$.

Sin embargo, como se puede imaginar por el hecho de que $\lfloor n/2^k \rfloor$ está cerca de a $n/2^k$, el exponente de 2 en $n!$ está muy cerca de la $n$; de hecho, es $n$ menos el número de 1s en el binario de expansión de $n$. De hecho, si $n$ es una potencia de 2, entonces el $2^{n-1}|n!$.