Find set with maximal cardinality given constraints We are given a set $A = \{1,2,3 \:...\:256 \}$. I'm obliged to find such A', so: 


*

*$A' \subset A$ 

*A' has the maximal possible cardinality

*A' contains no elements x,y which satisfy the following equality: $x = 2y$


I came up with some thoughts, but I'm not sure that my answer is correct, and I'm sure that the task could be solved in a more mathematically beautiful style.  
My reasoning was the following:
 1. First, pick up all odd numbers from set A. It makes 128 elements.
 2. Then, pick all even numbers, which are large enough to not comply with the equation $x = 2y$. They are $\{130, 132\:...\: 256\}$. It adds 64 elements.
 3. Then we note, that half of those 64 elements could be divided by 2 and some odd number from set A'. So we should only use those elements from previous step, which comply x div 4 = 0.
 4. Also, we can include some even numbers, which are small enough to not have and greater match. They are $\{2, 4\:...\: 64\}$. We have to skip every second of them, to not create new matches. It gives us another 16: $\{4,8,12\:...\: 64\}$. Though, we have skip every second of them again, since they build pairs with themselves. It's 8 now: $\{4,12\:...\: 32\}$
 5. Thus, we have 128 + 32 + 8 = 168, which is the maximal cardinality of A'.
I believe this solution lacks proof of maximality. So I would appreciate if you guys could prove my solution correct or erroneous or suggest more mathematically advanced way of approaching this problem (for example, I tried to look at elements of A as sequences of 8 bits, but it didn't help me much).
 A: I would split $A$ into subsets $A_0,\ldots,A_8$ where $A_i$ contains all numbers in $A$ with exactly $i$ powers of 2 in its factorization. Then $A_{i+1} \subset 2A_i$ and since the sets diminish in size the maximal subset would be $A_0\cup A_2\cup\ldots\cup A_8$. 
A: for some odd number $X$ in $A$, consider the sequence $X, 2X, 4X, 8X...$ The rule that no element can be twice another is equivalent to saying that we can take at most every second element from any such sequence. The only question then is whether to start at $X$ or $2X$. If the sequence has an even number of elements it doesn't matter, but otherwise we will get one more number by starting at $X$. 
def greatest_subset():
    result = []
    for i in range(1, 256, 2):
        while i <= 256:
            result.append(i)
            i *= 4
    return result

A: With use of Marc's helpful answer, I wrote a Python implementation in order to get the actual value of A's cardinality. We got 171, so my original analytical solution in the question body was wrong.
def find_max_cardinality_subset():
    As ={}
    for i in range(0,9):
        ai = []
        divisor = pow(2,i)
        for x in range(0, 257):
            if x % divisor == 0 and (x / divisor) % 2 != 0:
                ai.append(x)
        As[i] = ai
    all = 0
    for i in range(0,9, 2):
        all += len(As[i])

    print("it totals:", all)

A: I think by only rooting off the first observation that the odd subset [1,3,5,7...255] satisfies the initial condition, one can iteratively extract additional even elements from A based solely on the condition that they would hold no conflict with x=2y from A' already generated. My math formalism is terrible, I know. But this should answer the question.


*

*{1,3,5,7...255}             : 128 elements : Total 128


then 4*(subset 1) excluding those that go beyond the 256 limit
2. {4,12,20,28...1020} - {260,268...1020} : 128 - 96 = 32 elements : Total 160
then 4*{subset 2} excluding those that go beyond the 256 limit
3. {16,48,80...1008} - {272,304...1008} : 32 - 24 = 8 elements : Total 168
then 4*(subset 3) excluding those that go beyond the 256 limit
4. {64,192..960} - {320,448...960} : 8 - 6 = 2 elements : Total 170
The last remaining element that still fits within the limit is 4*64 = {256}
Capping the total at 171.
Feels a bit like brute force, but it works.
