Natural density of set $\{4^nk\}$, where $k$ is odd

Question

A starting point is this problem: $P \subset Z_n = \{1, 2, \dots, n\}$ is binary, if there exists a number $k$ such that both $k \in P$ and $2k \in P$, otherwise it is antibinary. One is supposed, for given $n$, to show antibinary set with maximum amount of elements (there might be many sets satisfying this property). One can show that set $P_n = \{4^m(2k + 1) \mid m, k \in \mathbb{N}\} \cap Z_n$ is a proper solution. My question is: how big is this set? I'm looking for $\displaystyle\lim_{n \to \infty} p_n$, where $p_n = \dfrac{|P_n|}{n}$. Simple program I wrote in Python suggests that the answer is $\dfrac{2}{3}$, but I don't know, how to prove it.

Answer 1

Since $4^m (2k+1)\leq n $ if and only if $k\leq\frac {n/4^m-1}{2}$, we have \begin{align} \frac {P (n)}n &=\frac 1n\sum_{m=0}^{\lfloor\log_4(m)\rfloor}\left\lfloor 1+\frac {n/4^m-1}{2}\right\rfloor\\ &=\frac 1n\sum_{m=0}^{\lfloor\log_4(m)\rfloor}\left\lfloor\frac {n+4^m}{2\cdot 4^m}\right\rfloor\\ &=\frac 1n\sum_{m=0}^{\lfloor\log_4(m)\rfloor}\frac {n+4^m}{2\cdot 4^m}+O\left(\frac {\log (n)}n\right)\\ &=\frac 12\sum_{m=0}^{\lfloor\log_4(m)\rfloor}\frac 1{4^m}+O\left(\frac {\log (n)}n\right)\\ &=\frac 23\left(1-4^{-1-\lfloor\log_4 (n)\rfloor}\right)+O\left(\frac {\log (n)}n\right)\\ &\xrightarrow {n\to\infty}\frac 23 \end{align}

Answer 2

Roughly $\frac 12$ of the numbers are of the form $2k+1$, $\frac 18$ of the numbers are of the form $8k+4$, $\frac 1{32}$ of the numbers are of the form $32k+16$, $\frac 1{128}$ are of the form $128k+64$, so the density is $$\frac 12\left(1+\frac 14+\frac 1{16}+\ldots\right)=\frac 18 \cdot \frac 1{1-\frac 14}=\frac 23$$