Eliminate numbers from $1,2,3. . .30$ such that the remaining sequence does not contain both $x$ and $2x$ BdMO 2014 nationals

From the sequence 1,2,3. . . .30,pick another sequence of numbers such that if x is in our new sequence,then 2x is not there(or vice versa).What is the maximum number of terms that can be in the sequence?

We pick the odd numbers and then some even numbers and find that the maximum number can be 20.But how to prove it?
 A: You can partition the set $\{1,2,\ldots,30\}$ into classes with the same greatest odd divisor (found by dividing by the highest power of$~2$ possible). There are as many classes as odd numbers, namely$~15$. All pairs $\{x,2x\}$ fall within one class. Each class is of the form $\{a,2a,4a,\ldots,2^ka\}$ for some $k\in\mathbf N$, and we can then choose at most $\lfloor k/2\rfloor+1$ elements from this class (picking the numbers $a,4a,4^2a,\ldots,4^{\lfloor k/2\rfloor}a$). The values of $\lfloor k/2\rfloor$ for $a=1,3,5,7,9,\ldots,29$ are successively $2,1,1,1,0,0,\ldots,0$, so that we can take at most $15+2+1+1+1=20$ elements.
A: Let me generalize the answer:
Say the given numbers are $$1,2,3,4...n$$
Let $f(n)$ denote the number of numbers which can be picked out of a sequence of first $n$ numbers as per the given condition.
 First we pick all the odd numbers. If $n$ is even we have $n/2$ odd numbers, else we have $(n+1)/2$ odd numbers. 
This can be collectively represented as $\lceil n/2\rceil$. Apart from these, the remaining numbers we have are:
$$2,4,6,8, 10... (\lfloor n/2\rfloor*2)$$ 
Out of these, the numbers which give odd quotient when divided by $2$ can be eliminated. So, the other numbers left are:
$$4,8,12....(\lfloor n/4 \rfloor*4)$$
We need to again freshly pick some numbers out of these $\lfloor n/4 \rfloor$ numbers using the same procedure, which means the number of such numbers will be $f(\lfloor n/4 \rfloor)$.
Hence the recursive solution is:
$$f(n)  = \lceil n/2 \rceil + f(\lfloor n/4 \rfloor)$$
The first few values of $f(n)$ starting from $n=1$ are:
$$1,1,2,3,4,4,5...$$
For your case, the answer is:
$f(30) = 15 + f(7)$
Here $f(7)= 4 + f(1) = 4+1=5$, hence the answer is $20$.
