|
Post by Devantè on Oct 15, 2006 10:54:28 GMT -5
A special number is a number which can be written as a sum of 2 or more consecutive numbers.
Prove that a number n is special iff it is not a power of 2.
I have a proof, but it took me 2 and a half pages, so I want to see if anyone can come up with something reasonable.
|
|
|
Post by Devantè on Oct 15, 2006 10:55:51 GMT -5
If a number n is special, then one of the following must be true:
n = k n = k + (k + 1) n = k + (k+ 1) + (k + 2) n = k + (k+ 1) + (k + 2) + ...
Where k <= n.
So expanding on this, we get:
n = k or n = 2k + 1 or n = 3k + 6 or n = 4k + 10 or ...
And so on for some positive integer k. First thing to notice is that all the odds other than 1 are covered because every odd number can be expressed as 2k + 1. So all we have left are the evens.
We can continue that pattern, getting more and more numbers, but it will get us nowhere (or so I think). We won't ever be able to say we have all the numbers.
So lets do the same thing, but write numbers a different way:
n = k n = k-1 + k + k+1 n = k-2 + k-1 + k + k+1 + k+2 n = k-a +... + k-1 + k + k+1 + ... + k+a
For some integers k or a. But we find something weird happens when we add those up;
n = k-1 + k + k+1 = 3k n = k-2 + k-1 + k + k+1 + k+2 = 5k n = k-a +... + k-1 + k + k+1 + ... + k+a = ak
So from this fact, we can construct a proof that if n is divisble by an odd number, it must be special.
Now if you know a little (but very important) fact, you can figure out where to go from here. But assuming you don't, that little fact is:
Every number can be written as a product of primes.
The only numbers that can be written as solely a product of 2's is a power of 2. Thus, for any non-power of two, there must be a prime in that product that is not 2. So it must be the case that...
... such a number is divisble by an odd number.
And that concludes that half of the proof (informally). The other half can be deduced by finding that any special number must contain a prime factor other than 2, and every power of two must contain only powers of 2, so they can't be equal.
|
|