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

• I think there are some in-between errors as well, as a result of which the final equation doesn't seem to hold always. I took a few examples to verify it! – Mathejunior Oct 31 '17 at 17:34

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