I am reading on this page a formula stating that the largest power of 2 contained (as a factor) in $n!$ has the following exponent:
$n -$ number of bits that are equal to $1$, in the binary representation of $n$
Can you explain, in the simplest possible way, why this is true. (I am aware of the Legendre formula, but right now I do not seem able to connect the dots.)
It does come out of Legendre's formula. First note that, for $n$ a power of $2$ $$\sum_{i=1}^\infty \left\lfloor \frac n{2^i}\right\rfloor=\frac n2+\frac n4+\ldots +1=n-1$$ and $n$ in binary has one $1$ bit, so the formula is satisfied. Now note that if $n,m$ are both powers of $2$ with $n \gt m$, $n+m$ has two bits and $$\sum_{i=1}^\infty \left\lfloor \frac {n+m}{2^i}\right\rfloor=\frac n2+\frac n4+\ldots +1+\frac m2+\frac m4+\ldots +1=n-1+m-1=n+m-2$$ because all the divisions come out even until the one where $2^i=m$, then the $n$ divisions are coming out even so we can ignore $m$ in the later ones. This extends to any number of summands.