2008 numbers

Do there exist a set of 2008 positive integers such that the sum of any subset of these is never a perfect square? If so provide proof of existence or construction, and if not then also provide proof.

Edit: I should mention that each of the numbers are distinct

{2, 8, 32, 128, 512, 2^11, 2^13, 2^15, etc, 2^4017}

I'm horrible at proofs, but I would suggest if you took that sequence out to 2008 terms, then you would have a set which met the conditions.

My initial line of thinking in terms of proof is that if you prime factored the sum of any proper subset, you would find that you would have an odd number of 2's in the prime factorization. Since square number have an even number of every prime number they are divisible by in, the result is clearly not a square.

You could sum none of them and get 0, but that's true of any subset, and not valid in my opinion.

Seems all right to me. But i am still not convinced that you will always get an odd number of 2's in the prime factorisation of the sum.

EDIT: I'm convinced now. Proof:

Take any subset, and consider the smallest element. Let this element be 2^2n+1. Then take each element of the subset mod (2^2n+2). Clearly, 2^2n+1 is congruent to 2^2n+1(mod 2^2n+2) and every other element is congruent to 0. The sum is therefore congruent to 2^2n+1(mod 2^2n+2) which is of course impossible for a perfect square. Well done geep.

EDIT2: Spelling.

Originally posted by geepamoogle
{2, 8, 32, 128, 512, 2^11, 2^13, 2^15, etc, 2^4017}

I'm horrible at proofs, but I would suggest if you took that sequence out to 2008 terms, then you would have a set which met the conditions.

My initial line of thinking in terms of proof is that if you prime factored the sum of any proper subset, you would find that you would have an odd number of could sum none of them and get 0, but that's true of any subset, and not valid in my opinion.

Originally posted by David113
Maybe it is easier to see if we use powers of 10:

Let the set be {10, 10^3, 10^5, 10^7, ... , 10^4015}.

The the sum of every non-empty subset ends with an odd number of 0's, so it cannot be a square.

In your proof, write the numbers in base 2 and add the numbers in the chosen subset. Again, it is obvious that there are no carries in the addition so ...[text shortened]... an odd number of 0's, but the square of every binary number ends with an even number of 0's.

he was talking about squares

*edit* and that ^10 is in base 2, nevermind...

Originally posted by David113
Maybe it is easier to see if we use powers of 10:

Let the set be {10, 10^3, 10^5, 10^7, ... , 10^4015}.

The the sum of every non-empty subset ends with an odd number of 0's, so it cannot be a square.

In your proof, write the numbers in base 2 and add the numbers in the chosen subset. Again, it is obvious that there are no carries in the addition so ...[text shortened]... an odd number of 0's, but the square of every binary number ends with an even number of 0's.

He is not saying that the binary representation has an odd number of zeroes, he is saying that the decimal representation has an odd number of zeros.