Take the 2-minute tour ×

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|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
add comment

4 Answers 4

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|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
add comment

Your Answer


