Greatest power of two dividing an integer

Question

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...

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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!

Answer 9

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.