To determine multiplicity of $2$ in $n!$ [duplicate]

Question

Is there a general formula for determining multiplicity of $2$ in $n!\;?$ I was working on a Sequence containing subsequences of 0,1. 0 is meant for even quotient, 1 for odd quotient. Start with k=3, k should be odd at start, if odd find (k-1) /2, otherwise k/2. This subsequence goes on until we reach 1.

Assign 0,1 accordingly as quotient is even, odd respectively. k(n+1) =k(n) +2, k(n) is odd, n>=1.Do this for all k>=3.1 is added before each subsequence as subsequence is generated by odd integer>=3.This sequence goes on like this: 11, 101, 111, 1001, 1101, 1011, 1111, 10001, 11001, 10101, 11101, 10011, 11011, 10111, 11111,..

The subsequences with increasing k are replica of the subsequence with steps to reach 1 minus one step or no of bits minus one with one extra bit of 1,0 depending on k.

Example-for k=5 the subsequence is 101 as quotient in first step is 2, and in second step is 1.

I want to find what is sequence at nth step? Also can this sequence help in determining what is multiplicity of 2 in n! ?

Answer 1

Hint:

$n!$ is the product of the numbers from $1$ to $n$.

How many multiples of $2$ are there in $\{1,2,...,n\}$?

How many multiples of $4$ are there in $\{1,2,...,n\}$?

How many multiples of $8$ are there in $\{1,2,...,n\}$?

...

Answer 2

You have Legendre's formula: for any prime $p$, the multiplicity of $p$ in $n!$ is $$v_p(n!)=\biggl\lfloor\frac{n}{p}\biggr\rfloor+\biggl\lfloor\frac{n}{p^2}\biggr\rfloor+\biggl\lfloor\frac{n}{p^3}\biggr\rfloor+\dotsm$$(of course, this is a finite sum).