Greatest power of two dividing an integer - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T02:54:03Z http://mathoverflow.net/feeds/question/29828 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer Greatest power of two dividing an integer Alex Lupsasca 2010-06-28T20:16:40Z 2010-10-04T09:00:04Z <p>Does anyone know of a <strong>closed form</strong> for the function on $\mathbb{N}$ which returns the greatest power of two which divides a given integer?</p> <p>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 <a href="http://en.wikipedia.org/wiki/Closed-form_expression" rel="nofollow">Wikipedia</a>.</p> <p>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...</p> <p>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$.</p> <p>Thanks!</p> <p>EDIT: I followed Gerry's answer and derived the following Fourier series for $f$:</p> <p>$$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)$$</p> <p>I will try to further simplify this...</p> http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer/29831#29831 Answer by Arturo Magidin for Greatest power of two dividing an integer Arturo Magidin 2010-06-28T20:31:27Z 2010-06-28T20:33:11Z <p>See <a href="http://www.research.att.com/~njas/sequences/A007814" rel="nofollow">Sloane's entry</a> 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})$,</p> http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer/29846#29846 Answer by Charles for Greatest power of two dividing an integer Charles 2010-06-29T00:24:37Z 2010-06-29T00:24:37Z <p>I think that given those operations (+, -, exp, log, and complex constants) it's probably not possible to create the 2-adic valuation.</p> http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer/29856#29856 Answer by Jacques Carette for Greatest power of two dividing an integer Jacques Carette 2010-06-29T01:49:35Z 2010-06-29T01:49:35Z <p>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.</p> <p>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 <em>representation-dependent</em> answer though. But that's because the representation-independent answers to this question will tend to be hopelessly inefficient.</p> http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer/29871#29871 Answer by Gerry Myerson for Greatest power of two dividing an integer Gerry Myerson 2010-06-29T06:36:54Z 2010-06-29T06:36:54Z <p>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$. </p> http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer/29877#29877 Answer by Wadim Zudilin for Greatest power of two dividing an integer Wadim Zudilin 2010-06-29T08:10:40Z 2010-06-29T10:51:41Z <p>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, <a href="http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P56.pdf" rel="nofollow">[J.M. Borwein and P.B. Borwein, <em>Amer. Math. Monthly</em> <strong>99</strong> (1992) 622-–640]</a> and links therein.</p> <p><strong>P.S.</strong> Some of you may enjoy classics---<a href="http://www.carma.newcastle.edu.au/wadim/MO/Liouville-1840.pdf" rel="nofollow">an elegant proof by J. Liouville from 1840 of the non-quadraticity of $e^2$</a>. The proof makes a very clever use of the $2$-adic order of $n!$</p> <p>If there is a closed form (in modern terminology) for this, why it couldn't be known by maitres?!</p> http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer/29973#29973 Answer by TonyK for Greatest power of two dividing an integer TonyK 2010-06-29T21:49:38Z 2010-08-22T23:20:20Z <p>It's easy if you allow yourself the XOR function: $f(n) = \log_2(((n$ XOR $(n-1)) + 1)/2)$.</p> <p><strong>Update</strong> It's even simpler using the bitwise AND function: $f(n) = \log_2(n$ AND -$n)$</p> http://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer/40281#40281 Answer by A.Neves for Greatest power of two dividing an integer A.Neves 2010-09-28T08:32:11Z 2010-10-04T09:00:04Z <p>Hi,</p> <p>Here is what I found</p> <p>$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}}}$</p> <p>This is a special case of $v_{m}(n)$ that differs a little from this one.</p> <p>For the general case the formula is</p> <p>$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}}}$</p> <p>Now, with this we can put together some arithmetical formulas</p> <p>the divisor functions</p> <p>$\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}}}$</p> <p>and the divisor summatory function defined as</p> <p>$\sigma_{0}=d(n)=\displaystyle\sum\limits_{k|n}1$</p> <p>and </p> <p>$D(x)=\displaystyle\sum\limits_{n \leq x}\sigma_{0}(n)$</p> <p>so for the divisor summatory function we have this formula</p> <p>$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.</p> <p>We can also express $\Omega(n)$ and $\omega(n)$ as sums over primes.</p> <p>Hope this helps.</p>