Greatest power of two dividing an integer - MathOverflow

Greatest power of two dividing an integer

2010-06-28T20:16:40Z

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 by Arturo Magidin for Greatest power of two dividing an integer

2010-06-28T20:31:27Z

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 by Charles for Greatest power of two dividing an integer

2010-06-29T00:24:37Z

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

Answer by Jacques Carette for Greatest power of two dividing an integer

2010-06-29T01:49:35Z

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 by Gerry Myerson for Greatest power of two dividing an integer

2010-06-29T06:36:54Z

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 by Wadim Zudilin for Greatest power of two dividing an integer

2010-06-29T08:10:40Z

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 by TonyK for Greatest power of two dividing an integer

2010-06-29T21:49:38Z

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 by A.Neves for Greatest power of two dividing an integer

2010-09-28T08:32:11Z

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.