Greatest power of two dividing an integer

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})$,

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.

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)$

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?!

I think that given those operations (+, -, exp, log, and complex constants) it's probably not possible to create the 2-adic valuation.

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.

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!

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.