Show that if $n \geq 2$ is even, then: $\frac {2n}{3} \leq \sum_{k=1}^{n} \frac{p(k)}{k} \leq \frac {2(n+1)}{3}$ Show that if $n \geq 2$ is even, then: $$\frac {2n}{3} \leq \sum_{k=1}^{n} \frac{p(k)}{k} \leq \frac {2(n+1)}{3}$$ where $p(k)$ is the greatest odd integer that divides $k$.

I think I'm almost done but cannot complete it. 
Well, it's known that there are $\frac {n}{2}$ odd naturals $ < n$. And for these integers, we have $\frac {p(k)}{k}=1$
Hence, we are left to show that: $$\frac {n}{6}\leq \sum_{k={\text {even}}, k\leq n}\frac{p(k)}{k}\leq \frac {n}{6} + \frac {2}{3}$$
Define $v_c(k)=d$ such that $c^d \mid k$ and $c^{d+1}\nmid k$.
If $k=2^x y$, then $\frac {p(k)}{k}=2^{-x}$. 
Hence, if we find of $v_2(k)=1, v_{2^2}(k)=1, v_{2^3}(k)=1, \cdots$ for $k=2,4,6, \cdots , n$, and multiply $2^{-r}$ to each $v_{2^r}$, we get the value of the equation.
Then, we can substitute it to show that it $\in [\frac {n}{6}, \frac{n+4}{6}]$
And the equation becomes, upon simplifying:
$$\frac {n}{6}\leq \sum_{x=1}^{e} \left\lfloor\frac{n-2^x}{2^{x+1}}\right\rfloor \leq \frac {n}{6}+\frac {2}{3}$$ where we assume $2^e \leq n < 2^{e+1}$ for some $e\in \mathbb{N}$.
But how to prove this? Maybe it's quite simple but I can't do it unfortuantely.
 A: As you found, we have
$$\frac{p(k)}{k} = 2^{-v_2(k)}.$$
Thus we can compute the sum if we know how many $k \leqslant n$ have $v_2(k) = m$ for every $m$. That's the number of multiples of $2^m$ not exceeding $n$ that are not multiples of $2^{m+1}$. The number of multiples of $r$ not exceeding $x$ is $\bigl\lfloor \frac{x}{r}\bigr\rfloor$, hence there are $\bigl\lfloor \frac{n}{2^m}\bigr\rfloor - \bigl\lfloor \frac{n}{2^{m+1}}\bigr\rfloor$ multiples of $2^m$ that aren't multiples of $2^{m+1}$ not exceeding $n$, and
$$\sum_{k = 1}^n \frac{p(k)}{k} = \sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl(\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - \biggl\lfloor \frac{n}{2^{m+1}}\biggr\rfloor\biggr).$$
The last sum is actually finite, since the terms are $0$ when $n < 2^m$, but $\infty$ is quicker to write. We can regroup this last sum,
\begin{align}
\sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl(\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - \biggl\lfloor \frac{n}{2^{m+1}}\biggr\rfloor\biggr)
&= \sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - \sum_{m = 0}^{\infty} \frac{2}{2^{m+1}}\biggl\lfloor \frac{n}{2^{m+1}}\biggr\rfloor \\
&= \sum_{m = 0}^{\infty} \frac{1}{2^m}\biggl\lfloor \frac{n}{2^m}\biggr\rfloor - 2 \sum_{k = 1}^{\infty} \frac{1}{2^k} \biggl\lfloor \frac{n}{2^k}\biggr\rfloor \tag{$k = m+1$} \\
&= n - \sum_{k = 1}^{\infty} \frac{1}{2^k}\biggl\lfloor \frac{n}{2^k}\biggr\rfloor.
\end{align}
Now $\lfloor x\rfloor \leqslant x$ yields, together with the fact that all but finitely many terms are $0$, so the inequality is strict for almost all terms,
$$\sum_{k = 1}^{\infty} \frac{1}{2^k} \biggl\lfloor \frac{n}{2^k}\biggr\rfloor < \sum_{k = 1}^{\infty} \frac{n}{4^k} = \frac{n}{3}$$
and hence we have the lower bound
$$\sum_{k = 1}^n \frac{p(k)}{k} > \frac{2n}{3}.$$
This also holds for odd $n$.
For the upper bound, the estimate $\lfloor x\rfloor > x-1$ is not enough, that would yield an upper bound of $\frac{2n}{3} + 1$ rather that the desired $\frac{2n+2}{3}$. But for integer $n$ we have $\bigl\lfloor \frac{n}{2^k}\bigr\rfloor \geqslant \frac{n}{2^k} - 1 + \frac{1}{2^k}$, and for even $n$, we have $\bigl\lfloor \frac{n}{2^k}\bigr\rfloor \geqslant \frac{n}{2^k} - 1 + \frac{2}{2^k}$, with a strict inequality for all large enough $k$, hence
\begin{align}
\sum_{k = 1}^{\infty} \frac{1}{2^k}\biggl\lfloor \frac{n}{2^k}\biggr\rfloor
&> \sum_{k = 1}^{\infty} \frac{1}{2^k}\biggl( \frac{n}{2^k} - 1 + \frac{a}{2^k}\biggr) \\
&= \frac{n}{3} - 1 + \frac{a}{3}
\end{align}
where $a = 1$ if $n$ is odd and $a = 2$ if $n$ is even. Thus we obtain
$$\frac{2n}{3} < \sum_{k = 1}^n \frac{p(k)}{k} < \frac{2n + (3-a)}{3},$$
and the upper bound $\frac{2(n+1)}{3}$ also holds for all $n$, and for even $n$ we can reduce it to $\frac{2n+1}{3}$.
