What is the size of the largest subset of the numbers 1 to n such that no number is twice as large as any other?

Question

Also, what is the size of the smallest subset of the numbers from 1 to n such that all the remaining numbers are either twice as great as or half as great as some number in the subset?

I believe that the answer to the first question may be two thirds n plus or minus 1.

This is how I arrived at 2n/3. Let S be a set of numbers such that no number is S is twice as great as any other number in S.

All numbers can be expressed as 2^ko where o is an odd number. If 2^ko is in S then 2^k-1o and 2^k+1o must be excluded from S. It follows that for each o, the best we can do is to include half the numbers 2^ko. Using n=100 as an example, the following procedure can be used.

Start by including the upper half of the set of numbers from 1 to 100. This gives us the numbers from 51 to 100 to be placed in S. For each odd number o from 1 to 100, there is a number y in the numbers from 51 to 100 where y = 2^ko and k is the maximum exponent such that the number does not exceed 100. Next consider all numbers x such that 2x goes from 51 to 100. This gives us 26 to 50, about a quarter of the numbers from 1 to 100, to be excluded from S. Now consider all the numbers that are half the numbers from 26 to 50, 13 to 25, about an eighth of the numbers from 1 to 100. Twice the value of these numbers maps to the excluded numbers 26 to 50, so we can include the numbers 13 to 25. Similarly, we must exclude the numbers from 7 to 12 and can include the numbers from 4 to 6

I hope it is clear that continuing this procedure and generalizing to all n, the number of entries included in S is (n/2 + n/8 + n/32 +...) = 2n/3. There will of course be rounding errors, but this should be a good approximation for large n. What I found by looking at specific cases is that it is an extremely good approximation even for relatively small n. I have not found a case where it was off by more than 1.

It is not difficult to find an algorithm to generate what seems to be a minimal set S for a number n such that no number is twice any other. The basic idea is that if we include a number 2^ko, we would like to include 2^k+3o. This forces the exclusion of 2^k+1o and 2^k+2o. I wrote a program to do this and I am generating sets of size about .571 times n.

Finally, the first problem can be generalized in an obvious way to find the largest subset S of numbers from 1 to n such that no number in S is c times greater than any other number in S. We note that any number can be expressed as c^kx, where x is not divisible by c. For each x, we again want half of the values c^kx. If you are willing to accept the previous 2/3 estimate, in an analogous fashion we get c/(c+1) for the general case. To see how we get the formula, instead of starting with numbers > n/2, we now start by placing into S numbers > n/c, of which there are n(1-1/c)=n(c-1)/c. We now alternately exclude and include subsets whose size is 1/c times the size of the previous inclusion/exclusion group. We end up with a total of n(c-1)/c times the geometric series in $1/c^2$, which simplifies to nc/(c+1).