Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking at the sum: $$f(n) = \sum_{k=1}^n m(k),$$ where $m(k)$ is defined by $2^{m(k)} || k$, i.e. $2^{m(k)}$ is the largest power of $2$ that divides $k$. For example, we have $f(8) = 0+1+0+2+0+1+0+3 = 7$. Here's a table of $n$, $m(n)$, and $f(n)$ for a few small $n$:

n     m(n)  f(n)
1     0     0
2     1     1
3     0     1
4     2     3
5     0     3
6     1     4
7     0     4
8     3     7

The values $m(n)$ in the table are the last $m(k)$-value for the given $n$, i.e. the value of $m(k)$ when $k=n$. I haven't spent much time trying to figure this out, mostly because it's a funny little problem and I thought I'd share it. It seems to me that we have $f(2^j) = 2^j-1 \forall j$ and $f(n)\sim n$.

share|cite|improve this question
Hmm... since when does $2^3$ divide $4$? :-) – Peter Košinár May 23 '13 at 14:52
All your $m$'s are one too high. – N. S. May 23 '13 at 14:57
OK -- the notation should be fixed now and consistent with the answers. – Douglas B. Staple May 23 '13 at 15:15
up vote 5 down vote accepted

Let $m(k)$ be the exponent of $2$ occurring in $k$, i.e. $2^{m(k)}\|k$. One quickly deduces $$\tag1f(2n+1)=f(2n)=n+f(n)$$ as only the even numbers contribute and $2k$ contributes one more to $2n$ and $2n+1$ than $k$ does to $n$, i.e. $m(2k)=m(k)+1$. Since $f(1)=m(1)=0$, we find $f(3)=f(2)=1$, $f(5)=f(4)=3$, and so on. The sequence goes $$ 0, 1, 1, 3, 3, 4, 4, 7, 7, 8, 8, 10, 10, 11, 11, 15, 15, 16, 16, 18, 18, 19, 19, 22, 22, 23, 23, 25, 25, 26, 26,\ldots$$ And according to OEIS, this equals $m(n!)$ and also $n$ minus the number of $1$s in the binary expansion of $n$. One easily verifies that these two discriptions indeed follow the recursion formula $(1)$.

share|cite|improve this answer

There is a name for your "m" function, it is called the 2-adic valuation, and is usually denoted by $\nu_2$.

It is easy to show that


Indeed, for $1 \leq k \leq j-1$ there are exactly $2^{j-k-1}$ numbers between $1$ and $2^j$ with $\nu_2(n)=k$, namely

$$\{ 2^k\cdot 1, 2^k \cdot 3, 2^k \cdot 5,..., 2^k\cdot (2^{j-k}-1) \}$$

When $k=n$ there is exactly $1$ number with $\nu_2(n)=k$.

Then, by rearranging the terms of your sum into groups of equal terms you get

$$f(2^j)=j+\sum_{k=1}^{j-1} k 2^{j-k-1}$$

It is easy to show that this sum is exactly $2^j-1$.

Edit With the new fix, you need to add a 1 to every single term, thus the sum increases by exactly $2^j$.

share|cite|improve this answer

As a bit of interesting trivia concerning $f(n)$ we see that the Mellin-Perron summation formula applies, giving $$ f(n) = \frac{1}{2} v_2(n) + \frac{1}{2\pi i} \int_{3/2-i\infty}^{3/2+i\infty} L(s) n^s \frac{ds}{s} \quad\text{where}\quad L(s) = \sum_{n\ge 1} \frac{v_2(n)}{n^s}.$$ But we have $$ L(s) = \sum_{m\ge 1} \frac{v_2(2m)}{(2m)^s} = \frac{1}{2^s} \sum_{m\ge 1} \frac{1+v_2(m)}{m^s} = \frac{1}{2^s} (\zeta(s) + L(s)),$$ so that $$ L(s) = \frac{\zeta(s)}{2^s-1},$$ giving $$ f(n) = \frac{1}{2} v_2(n) + \frac{1}{2\pi i} \int_{3/2-i\infty}^{3/2+i\infty} \frac{\zeta(s)}{2^s-1} n^s \frac{ds}{s}$$

We can apply the Cauchy Residue Theorem to this integral, treating first the poles at $s=1$ and $s=0$, which yields $$f(n) \sim \frac{1}{2} v_2(n) + n - \frac{1}{2}\log_2 n - \frac{1}{4} - \frac{1}{2}\log_2 \pi.$$ The above approximation is excellent, giving for example $f(200) \sim 196.6023238$ when the correct value is $197$, or $f(411) \sim 405.5827546$ when the correct value is $405.$ Finally, $f(1000)$ is $994$ when the approximation gives $995.4413598.$

The complete asymptotic expansion is obtained by including all the poles on the imaginary axis at $\frac{2\pi i k}{\log 2}$, with $k$ a nonzero integer. These poles are all simple. We have $$\operatorname{Res}\left(\frac{1}{2^s-1}; s = \frac{2\pi i k}{\log 2}\right) = \frac{1}{\log 2}.$$ Now introducing $$\rho_k = \frac{2\pi i k}{\log 2}$$ we finally obtain $$f(n) \sim \frac{1}{2} v_2(n) + n - \frac{1}{2}\log_2 n - \frac{1}{4} - \frac{1}{2}\log_2 \pi + \frac{1}{\log 2} \sum_{k\in \mathbb{Z}\setminus 0} \frac{\zeta(\rho_k)}{\rho_k} e^{2\pi i k\log_2 n},$$ where the sum is a Fourier series in $\log_2 n$ that describes the fluctuations.

Taking the terms up to $|k|=7$, we obtain $f(200) \sim 197.0498970.$ With $34$ terms, we obtain $f(411)\sim 405.3130370$ and $f(1000) \sim 993.9869087.$

share|cite|improve this answer

One simplification of the sum is $f(n)=\sum\limits_{k=1}^\infty \left\lfloor\frac{n}{2^k}\right\rfloor$
(obviously, only terms for $k\leq \log_2(n)$ are going to be non-zero). This can be evaluated very easily on the computer, since each consecutive term corresponds to dividing the previous one by 2 and ignoring any remainder.

share|cite|improve this answer
This is interesting; the point is to count the number of integers $\leq n$ divisible by $2^k$ for each $k\geq 1$, which is exactly $f(n)$. This also immediately gives $f(2^j) = 2^j-1$ as the sum of a geometric series. – Douglas B. Staple May 24 '13 at 17:36
Answer updated to reflect the modification in question. – Peter Košinár May 24 '13 at 19:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.