TITLE: $\sum_{k=1}^n m(k)$, where $m(k)$ is defined by $2^{m(k)} || k$.
QUESTION [3 upvotes]: 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$.

REPLY [3 votes]: 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.$
{"set_name": "stack_exchange", "score": 3, "question_id": 400265}