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

-
The function $f:\mathbb{N}\to\mathbb{N}_0$ defined by $n=2^{f(n)}q$ where $q$ is an odd integer is a function. Don't forget the maxim: "a function is not a formula". – Robin Chapman Jun 28 2010 at 20:24
If you're using "function" to mean "formula," you're asking the wrong question; I assume what you want is just to compute f quickly. If you're using "function" to mean "algorithm," whatever happened to dividing repeatedly? – Qiaochu Yuan Jun 28 2010 at 20:29
@Qiaochu: Rather than the question being wrong, the comment should be to ask Alex what "usable" means. – Dror Speiser Jun 28 2010 at 20:35
Very few functions have closed forms. Do you have any reason to expect that this function does, and/or would you be interested in a proof that no closed form exists? – Qiaochu Yuan Jun 28 2010 at 21:25
In my experience, the meta-mathematical term "closed-form expression" is used in combinatorics, analysis, and differential algebra. It can be defined for number-theoretic functions, but, of course, one would have to carefully stipulate what the building blocks should be. To me, $\operatorname{ord}_2$ seems a reasonable primitive. – Victor Protsak Jun 28 2010 at 22:37

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

-
Isn't that a satisfactory answer?! Write $n$ as $n!/(n-1)!$ and then use the standard formula for the $p=2$ order (mathoverflow.net/questions/26336); there is another formula $(n-S_p(n))/(p-1)$ where $S_p(n)$ is the sum of digits in $p$-record of $n$. – Wadim Zudilin Jun 29 2010 at 7:37
Thanks for your answer! This is essentially the same idea that I used to construct my $f(n)$, except I used products of cosine squared terms to determine divisibility by $2^i$. And you are right: it's not an infinite sum, since you only need to consider $\rho(n)$ terms. Sadly, it's still not what I'm looking for; ideally, I'd love to find something involving trig functions... – Alex Lupsasca Jun 29 2010 at 22:22
Well, if it's trig functions you want, you can replace $[x]$ with $x-\lbrace x\rbrace$, and then expand $\lbrace x\rbrace$ in Fourier series. Of course, that will give you infinite series.... – Gerry Myerson Jun 30 2010 at 1:22
Thank you Gerry! This is useful to me :) – Alex Lupsasca Jun 30 2010 at 20:28
You're quite right, but maybe this works. Define $((x))$ to be 0 if $x$ is an integer, $\lbrace x\rbrace-(1/2)$ otherwise. Then $((x))$ is periodic and odd and its Fourier series converges to it everywhere. I think that $Q(n,k)=(1/k)-(((n/k))-(((n-1)/k)))$ is $1/2$ if $k$ divides $n$ or $n-1$ and 0 otherwise. If $n$ is even, and $k$ is a power of 2, then $k$ won't divide $n-1$, so $2Q(n,k)$ will give 1 if $k$ divides $n$ and 0 otherwise. So at least for even $n$, $2(Q(n,2)+Q(n,4)+Q(n,8)+\dots)$ may do what you want. – Gerry Myerson Jul 1 2010 at 1:10

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

-
Arturo, while this is useful information it does not address the meaning of the question as I currently understand it. – Qiaochu Yuan Jun 28 2010 at 21:29
Since this is a function from $\mathbb{N}$ to $\mathbb{N}$, Sloane's is at least a good first stop; when I gave the link, the question still asked for "formulas", as opposed to closed forms expressions; and I didn't delve too deeply into the references given in Sloane's. – Arturo Magidin Jun 29 2010 at 2:19
Hmm, I guess checking Sloane's should've been my first reflex; lesson learned :) I wonder if it is possible to find a formula for the $n^{\text{th}}$ coefficient in this series; if that were the case, this would be an entirely satisfactory answer... As it stands, I believe this comes closest to answering my question! Thanks a lot for your input :) – Alex Lupsasca Jun 29 2010 at 22:32

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.

-
Reminds me of a story told by a professor I had in undergraduate, of a guy who came to him very excited because he had come up with an easy divisibility test to determine if any given integer $n$ was divisible by any given positive integer $d>1$: just write $n$ in base $d$ and see if the last digit is a $0$. – Arturo Magidin Jun 29 2010 at 2:33
@Arturo: indeed! If the question had been about the 5-adic representation, I probably wouldn't have responded so glibly. But since binary comes so naturally to computers, and the point was to 'compute', I did not think my answer was so out of line. – Jacques Carette Jun 29 2010 at 11:54
Thanks a lot for your answer! Using the representation in base two is indeed a cheap move, and not exactly what I was looking for :) Nevertheless, I must confess that I hadn't considered it, and that it might actually prove useful for me! And it does indeed make it very easy to "compute", so thanks again! – Alex Lupsasca Jun 29 2010 at 22:24
@Jacques: No, it was absolutely not out of line; if you were going to program this into a computer, a bitwise operation/algorithm like you suggest is not only very natural, it is likely to be much faster than trying to program some fancy evaluation since bitwise operations are often already implemented. I did not mean to imply the response was out of line, I just honestly was reminded of a funny anecdote I kind of felt like sharing. Sorry that I wasn't clear, especially if it seemed like a criticism. – Arturo Magidin Jun 30 2010 at 5:23

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

-
Wow, thanks for the link to that paper. While the results contained therein are not directly relevant to me, they are certainly of considerable mathematical beauty! Now, from your answer, and that of Jacques Carette, it seems that the key is finding a closed form expression for the binary digit formula... Unfortunately, it would seem that no (reasonably simple) expression exists for it...? – Alex Lupsasca Jun 29 2010 at 22:28
Unfortunate things happen quite often: I won't expect a closed formula for the digit sum exists. – Wadim Zudilin Jun 29 2010 at 22:50

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

-
Hum, this looks very intriguing but I must admit I don't fully understand it... Is this XOR function a bitwise operation? If so, then this means working in base 2, like Jacques Carette suggested? Or am I missing something? – Alex Lupsasca Jun 29 2010 at 22:37
XOR is 'exclusive-or'. All assembly-language programmers are intimately acquainted with it. For non-negative integers a and b, a XOR b is the non-negative integer whose binary expansion is 1 in exactly those positions where the binary expansions of a and b differ. In our case, n XOR (n-1) wipes out all the 1's except the least significant, and changes any less-significant 0's to 1. E.g.: 12 XOR 11 = 7 (in binary: 1100 XOR 1011 = 0111); 19 XOR 18 = 1 (in binary: 10011 XOR 10010 = 00001). – TonyK Jun 29 2010 at 22:49
This method is a more complicated version of mine. It would be more useful than mine if it generalized to other bases, but it is not clear how to do so. But it is definitely base-2 dependent. – Jacques Carette Jul 1 2010 at 21:50
Donald E. Knuth suggests $f(n) = \log_2(n \& (n-1))$ (The Art of Computer Programming Vol. 4, Fascicle 1, p. 8), where $\&$ is the bitwise AND operation. – jp Jul 27 2010 at 19:11
This type of answer is much more useful than the others to anyone actually writing computer programs that depend on calculating the 2-adic norm. – David Eppstein Aug 23 2010 at 1:01

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

-
Could you explain your use of probably? – François G. Dorais Jun 29 2010 at 0:32
I am more curious about the meaning of *complex constants*: mathoverflow.net/questions/28612/… :-) – Wadim Zudilin Jun 29 2010 at 2:04
I think Charles means one can construct trig functions. I agree with his "probably"; my intuition about elementary functions is that they are sums of products of a monotonic factor and a periodic factor (whose period may vary), and this does not reproduce the behavior of the 2-adic valuation. – Qiaochu Yuan Jun 29 2010 at 4:11
Yes, multiplication, division, and trig functions come along free. My intuition doesn't match yours regarding elementary functions, though. The various extensions to Richardson's theorem show a sharp difference between elementary functions (+, -, exp, log, sin over R) and elementary functions with restricted composition of sin is sharp: the constant problem is undecidable in the first but decidable in the second. – Charles Jun 29 2010 at 6:39
I am not at all familiar with this area of mathematics; could anyone tell me if it is possible to prove such a thing (that is, Charles' claim that "it's probably not possible to create the 2-adic valuation" using elementary functions), and if so, how would one go about doing it? – Alex Lupsasca Jun 29 2010 at 22:29

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.

-
 Thanks! Did you derive this yourself, or could you point me to a reference? – Alex Lupsasca Sep 29 2010 at 5:38