<s>[INST] Prove that $0<\sum_{k=1}^n \frac{g(k)}{k} - \frac{2n}{3} < \frac{2}{3}$ Prove
$$0<\sum_{k=1}^n \frac{g(k)}{k} - \frac{2n}{3} < \frac{2}{3}$$
where $g(k)$ is the greatest odd divisor of k
Please Find Holes in my Proof.
Let $k=2m+1$ if we show that the right hand side of the equation is true for odd numbers, then it is true for even numbers since there is a net total of $1/3$ since $g(k)/k = 1$ for odd numbers.
$$\sum_{k=1}^n\frac{g(k)}{k} <\frac{2n}{3} + \frac{2}{3}$$
$$\sum_{k=1}^n\frac{g(k)}{k} <\frac{2(2m+1)}{3} + \frac{2}{3}$$
$$\sum_{k=1}^n\frac{g(k)}{k} <\frac{4m}{3} + \frac{4}{3}$$
From $1$ to $2m+1$ there are $m$ even numbers and $m+1$ even numbers, the value of $\frac{g(k)}{k}$ for even numbers is $\frac{1}{2^{V2(k)}}$ where $V2(k)$ is the exponent of 2 in the factorization of k
$$\sum_{k=1}^n\frac{g(k)}{k}  = m+1 + (m)\frac{1}{2} -((\lfloor{\frac{m}{2}\rfloor \frac{1}{4}) +(\lfloor{\frac{m}{4}\rfloor \frac{1}{8}}})...)$$
$$\leq    m+1 + (m)\frac{1}{2} - (\frac{m}{8} + \frac{m}{32}...) = \frac{4m}{3} + 1 <\frac{2(2m+1)}{3} + \frac{2}{3}$$ 
Solving for the left hand side of the inequality
$$0<\sum_{k=1}^n \frac{g(k)}{k} - \frac{2n}{3}$$ Let $k = 2m$ with the same reasoning as above
$$\sum_{k=1}^n\frac{g(k)}{k}  = m + (m)\frac{1}{2} -((\lfloor{\frac{m}{2}\rfloor \frac{1}{4}) +(\lfloor{\frac{m}{4}\rfloor \frac{1}{8}}})...)$$
$$\geq    m + (m)\frac{1}{2} - (\frac{m}{8} + \frac{m}{32}...) = \frac{4m}{3} + \frac{1}{3} >\frac{2(2m)}{3}$$ 
I'm not sure about the solution since it was a strict inequality to begin with. Is this a correct solution? Any other solutions are welcome
 [/INST] $$g(2^m (2k+1))=2k+1$$ Let $$h(n)  = \sum_{2k+1 \le n} 1=\lfloor (n+1)/2\rfloor$$ then $$\sum_{k=1}^n \frac{g(k)}{k} =\sum_{m\ge 0} \frac{h(n/2^m)}{2^m}=\sum_{m\ge 0} \frac{\lfloor (n/2^m+1)/2\rfloor}{2^m}=\sum_{m\ge 0} \frac{ (n/2^m+1)/2-O(1)}{2^m}\\ = \frac{n/2}{1-2^{-2}}+\frac{1/2}{1-2^{-1}}-\frac{O(1)}{1-2^{-1}}=\frac23 n+1-2 O(1)$$
where here $O(1) \in [0,1)$
</s>