Greatest power of two dividing an integer Does anyone know of a closed form for the function on $\mathbb{N}$ which returns the greatest power of two which divides a given integer?
To be more precise, any positive integer $n\in\mathbb{N}$ can be uniquely expressed as $n=2^pq$ where $p,q\in\mathbb{N}$ and furthermore $q\equiv1\mod2$. I am looking for a closed form of the resulting function $f:\mathbb{N}\to\mathbb{N}$ which is such that $f:n\mapsto p$, as defined e.g. on Wikipedia.
As a starting point, I constructed a summation which does the job:
$$f(n)=\sum_{j=1}^{\rho(n)}\left(\prod_{i=1}^{j}\cos\left[\frac{\pi n}{2^i}\right]\right)^2$$
where $\rho(n)=\lfloor\log_2n\rfloor$. Sadly, this expression is not very useful, and I would prefer a closed form expression. Using Morrie's Law, the product can be converted to a limit as follows:
$$f(n)=\lim_{\epsilon\to0}t[\pi(n+\epsilon),\rho(n)]$$
where
$$t[x,m]=\sum_{j=1}^{m}\left(\frac{2^{-j}\sin[x]\cos[x]}{\sin[2^{-j}x]}\right)^2$$
However, I cannot find a closed form for this summation...
So in summary, I'd be grateful if anyone could give me an expression for $t(x,m)$ which would make my version of $f$ usable, or if anyone could tell me another such $f$.
Thanks!
EDIT: I followed Gerry's answer and derived the following Fourier series for $f$:
$$f(n)=(1+\cos[\pi n])\left(1-2^{-\rho(n)}+\sum_{j=1}^{\rho(n)}\sum_{k=1}^\infty\frac{\sin[2\pi k n 2^{-j}]-\sin[2\pi k (n-1) 2^{-j}]}{k}\right)$$
I will try to further simplify this...
 A: Note that this $f$ is computable, and thus corresponds to a (finite size) lambda term.  So, in that sense, it has a closed-form.  Of course, if you use a different base language for what you mean by closed-form, this may disappear.  On the other hand, by using Goedel numbering, we can encode this lambda term as an arithmetic function -- which will most surely be absolutely hideous.
Now, if the real question is, is there an easy way to compute this, the answer is yes, very easy: represent your $n$ in binary, and count the number of trailing 0s -- that number is the $f(n)$ you seek.  This is a representation-dependent answer though.  But that's because the representation-independent answers to this question will tend to be hopelessly inefficient.
A: It's easy if you allow yourself the XOR function: $f(n) = \log_2(((n$ XOR $(n-1)) + 1)/2)$.
Update It's even simpler using the bitwise AND function: $f(n) = \log_2(n$ AND -$n)$
A: From Gerry's answer it follows that the existence of closed form for the required function
is reduced to the existence of closed formula for $S_2(n)$, the sum of digits in the binary
record of $n$. Note that a reasonable generating function for this series,
$$
\sum_{n=0}^\infty x^{S_2(n)}q^n
=\prod_{n=1}^\infty (1+xq^{2^n})
$$
is well studied in transcendence number theory; see, for example,
[J.M. Borwein and P.B. Borwein, Amer. Math. Monthly 99 (1992) 622-–640] and links therein.
P.S. Some of you may enjoy classics---an elegant proof by J. Liouville from 1840 of the non-quadraticity of $e^2$. The proof makes a very clever use of the $2$-adic order of $n!$
If there is a closed form (in modern terminology) for this, why it couldn't be known by maitres?!
A: I think that given those operations (+, -, exp, log, and complex constants) it's probably not possible to create the 2-adic valuation.
A: Hi,
Here is what I found
$f(n)=v_{2}(n)=\displaystyle\sum\limits_{r=1}^{\infty}\frac{r}{2^{r+1}}\sum\limits_{k=0}^{2^{r+1}-1}e^{\frac{2k\pi i(n+2^{r})}{2^{r+1}}}$
This is a special case of $v_{m}(n)$ that differs a little from this one.
For the general case the formula is
$v_{m}(n)=\displaystyle\sum\limits_{r=1}^{\infty}\frac{r}{m^{r+1}} \sum_{j=1}^{(m-1)} \sum\limits_{k=0}^{(m^{r+1}-1)}e^{\frac{2k\pi i(n+(m-j)m^{r})}{m^{r+1}}}$
Now, with this we can put together some arithmetical formulas
the divisor functions
$\sigma_{a}(n)=1+\displaystyle\sum_{m=2}^{\infty}\sum_{r=1}^{\infty}\frac{m^a}{m^{r+1}} \sum_{j=1}^{(m-1)} \sum\limits_{k=0}^{(m^{r+1}-1)}e^{\frac{2k\pi i(n+(m-j)m^{r})}{m^{r+1}}}$
and the divisor summatory function defined as
$\sigma_{0}=d(n)=\displaystyle\sum\limits_{k|n}1$
and 
$D(x)=\displaystyle\sum\limits_{n \leq x}\sigma_{0}(n)$
so for the divisor summatory function we have this formula
$D(n)=\displaystyle\sum_{m=2}^{\infty}\sum_{r=1}^{\infty}\frac{r}{m^{r+1}} \sum_{j=1}^{(m-1)} \sum\limits_{k=0}^{(m^{r+1}-1)}e^{\frac{2k\pi i(p^n+(m-j)m^{r})}{m^{r+1}}}$ where $p$ is some arbitrary fixed ($2$ for example) prime number.
We can also express $\Omega(n)$ and $\omega(n)$ as sums over primes.
Hope this helps.
A: See Sloane's entry for the sequence, which is A007814. which includes a recursive by-cases formula, and the generating function $A(x) = \sum_{k=1}^{\infty}(x^{2^k})/(1-x^{2^k})$,
A: I suspect this answer will not be found satisfactory, but here goes. Write $[x]$ for the integer part of $x$. Then $[n/2]-[(n-1)/2]$ is 1 if $n$ is a multiple of 2, 0 otherwise. $[n/4]-[(n-1)/4]$ is 1 if $n$ is a multiple of 4, 0 otherwise. Etc. So the function you want is $$[n/2]-[(n-1)/2]+[n/4]-[(n-1)/4]+[n/8]-[(n-1)/8]+\dots$$ where the sum isn't really infinite, it has $r$ terms, where $r$ is something like $\log_2n$. 
A: Here is a formula that I found:
$$ \sum_{a=1}^{\lfloor log_2(n) \rfloor}(\lfloor \frac{n}{2^a} \rfloor + \lfloor \frac{-n}{2^a} \rfloor + 1) $$
It gives the $r$ of the largest $2^r$ divides any integer $n$. It uses the expression
$$ \lfloor x \rfloor + \lfloor -x \rfloor + 1 $$
which gives $1$ if $x$ is an integer and $0$ otherwise. Using $\frac{n}{2^a}$ instead of $x$ effectively gives $1$ if $n$ is divisible by $2^a$ and $0$ if not. Summing these for larger values of $a$ gives you the highest $2^r$ it can be divided by. The equation
$$ \sum_{a=1}^{\lfloor log_b(n) \rfloor}(\lfloor \frac{n}{b^a} \rfloor + \lfloor \frac{-n}{b^a} \rfloor + 1) $$
easily generalizes it to the highest exponent of $b$ dividing into $n$. You can also multiply $2$ with either itself or $1$ instead of adding $1$ or $0$, which gives the full $2^r$:
$$ \prod_{a=1}^{\lfloor log_2(n) \rfloor}(\lfloor \frac{n}{2^a} \rfloor + \lfloor \frac{-n}{2^a} \rfloor + 2) $$
Generalizing this for any factor $b^r$ is slightly more complicated, but still simple:
$$ \prod_{a=1}^{\lfloor log_b(n) \rfloor}((b-1)(\lfloor \frac{n}{b^a} \rfloor + \lfloor \frac{-n}{b^a} \rfloor) + b) $$
The multiplication by $b-1$ is required because $ \lfloor x \rfloor + \lfloor -x \rfloor $ by itself gives $0$ for integers and $-1$ for other numbers. Multiplying it by $b-1$ and adding $b$ simply makes it multiply by $b$ if $\frac{n}{b^a}$ is an integer and $1$ if it is not, so that the product gives $b^r$. Hope this helps!
A: I add my fanciful useless formula too:
$$f(n) = \nu_2(n) = \log_2 \left[n - \sum_{k=0}^{\lfloor \log_2{n} \rfloor}\left(\left\lfloor\frac{2n-1+2^{k+1}}{2^{k+2}}\right\rfloor - \left\lfloor\frac{2n-1+2^{k+2}}{2^{k+3}}\right\rfloor - \left\lfloor \frac{n}{2^{k+2}} \right\rfloor\right)2^k \right] + \frac{1+(-1)^n}{2}$$
For an explanation see here.
