nicetry007 wrote: In the set $ \{1, 2, \cdots, 2^{n}\}$, the number of positive integers that are divisible by $ 2^{k}$, $ 1 \leq k \leq n-1$ is $ 2^{n-k}$. Of these $ 2^{n-k}$, exactly half of them have $ 2^{k}$ as the higest power of $ 2$ dividing them. For these numbers, the ratio $ \frac{p(m)}{m}= \frac{1}{2^{k}}$. The contribution of these numbers towards the sum is $ \;\frac{1}{2}2^{n-k}\frac{1}{2^{k}}= \frac{1}{2^{2k-n+1}}$. The contribution from odd numbers is $ 1\cdot 2^{n-1}$. Finally, the contribution from $ 2^{n}$ is $ \frac{1}{2^{n}}$. Taking the sum of all the contributions, we get $ \frac{1}{2^{n}}\sum_{k=1}^{2^{n}}\frac{p(k)}{k}\; =\; \frac{1}{2^{n}}\left(2^{n-1}\;+\;\frac{1}{2^{n}}\;+\;\sum_{k = 1}^{n-1}\frac{1}{2^{2k-n+1}}\right)$ $ =\; \frac{1}{2^{n}}\left(\;\frac{1}{2^{n}}\;+\;\sum_{k = 0}^{n-1}\frac{1}{2^{2k-n+1}}\right)\; =\; \frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;+\; 2^{n-1}\sum_{k = 0}^{n-1}\frac{1}{2^{2k}}\right)\;=\; \frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;+\; 2^{n-1}\left(\frac{1\;-\; \frac{1}{2^{2n}}}{1 \;-\; \frac{1}{2^{2}}}\right)\right)\;= \;\frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;+\; 2^{n+1}\left(\frac{1\;-\; \frac{1}{2^{2n}}}{3}\right)\right)$ $ = \;\frac{2}{3}\;+\;\frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;-\; \frac{2}{3}\left(\frac{1}{2^{n}}\right)\right) \;=\; \frac{2}{3}\;+\; \;\frac{1}{4^{n}}\left(1\;-\; \frac{2}{3}\right)\; =\; \frac{2}{3}\;+\; \;\frac{1}{3 \cdot 4^{n}}\; > \; \frac{2}{3}$

If $ k = 2^lm, \ m - odd$, then $ m = p(k),\frac {p(k)}{k} = 2^{ - l}$. Therefore \[ \frac {1}{2^n}\sum_{k = 1}^{2^n}\frac {p(k)}{k} = \frac {1}{2^n}\sum_{l = 0}^n\frac {2^{n - l - 1}}{2^l} = \frac 12 \sum_{l = 0}^n\frac {1}{4^l} = \frac {2 - 2^{ - 2n - 1}}{3} < \frac 23. \] Modedit: this is wrong... first equality in particular (and as a result the conclusion).

Here is a different solution that all of the above. Set $a_n = \sum_{k=1}^{2^n}\frac{p(k)}{k}$. Noting $p(k)=k$ for $k\equiv 1\pmod{2}$, we have $a_n = 2^{n-1}+\sum_{k'=1}^{2^{n-1}} \frac{p(2k')}{2k'} = 2^{n-1}+\frac12 a_{n-1}$, since $p(2k')=p(k')$. Now, we prove by induction that $a_n>\frac{2^{n+1}}{3}$, which is the claim. The base case is clear, and suppose $a_{n-1}>2^n/3$. Then, $a_n > 2^{n-1}+\frac12 a_{n-1}>2^{n+1}/3$, as desired.