Powers of 2 Proof

Date: 03/24/2003 at 10:52:18
From: John
Subject: Powers of 2

Prove that any number that is not a power of 2 can be expressed as a 
sum of two or more consecutive positive integers, but that this is 
not possible for powers of 2.

The case for an odd number is simple enough, but even numbers are a 
little more difficult. I have tried to find some random values (i.e. 
10, 42, 68) and have found that it is possible, but don't know how to 
show this in general, or how to prove it is false for powers of 2.

Date: 03/26/2003 at 10:13:56
From: Doctor Jacques
Subject: Re: Powers of 2

Hi John,

This is a nice problem.

As you point out, the case where N is odd and >= 3 is trivial:

  2n + 1 = n + (n+1)

We will show that, if we can express N as required, we can also 
express 2*N. As every number that is not a power of 2 can be written 
as:

  N = a * 2^b

where a is odd and >= 3, the result will follow by induction on b.

Let N be the sum of k terms: N = a + ... + (a + k - 1)

We distinguish two cases, depending on the parity of k.

k odd
-----

By the formula for an arithmetic progression, we have:

  N = k * (2a + k - 1) / 2

and this shows that N is a multiple of k. In this case, we add N/k to 
each term.

k even
------

Let k = 2m. Starting with the sequence:

   a, a+1, .... , b-1, b

of even length, we extend it both ways by adding m terms on each side:

  a-m, a-m+1, ..., a-1 , a, ... b, b+1, b+m

It is easy to see that the sum of the new sequence is 2N, since the 
sum of extreme terms is constant.

Of course, the problem is that some terms on the left may be 0 or 
negative. In that case, we delete 0, and, starting with -1, we cancel 
each negative term with its opposite. This will leave a sequence of 
consecutive and positive integers.

This is possible, since there are at most (m-1) negative terms 
(because of the 0). This means that we must remove at most (m-1) 
positive terms, starting at 1. As we started with 2m terms and added 
m terms on the right, this is always possible, and, in particular, 
the new sequence will always be longer than the old. This does not 
exclude the possibility that there exists a shorter sequence for a 
given N.

To show that the problem has no solution if N is a power of 2, we go 
back to the formula for the arithmetic progression:

  N = k*(a + b)/2

where k is the number of terms, and a and b are the first and last 
terms. If N is a power of 2, k must be even, and this shows that N is 
a multiple of (a+b). However, if k is even, a+b is odd, yielding a 
contradiction.

There is another method to solve this problem. If N is not a power of 
2, N is divisible by an odd factor p >= 3 (we can take, for example, 
the smallest odd prime factor of N).

You can express N as a sum of p terms, centered on N/p, as you can 
easily check. Of course, there may also be some simplification of 
negative terms, as in the previous method; p is only an upper bound of 
the number of terms (for example, if you start with N = p, an odd 
prime, you will end up with only two terms after simplification).

Which method gives the shortest answer may depend on the number N. In 
either method, there is some choice for the selection of the factors -
maybe you can always end up with the same result (I don't know).

Concerning sums of consecutive odd numbers, I believe that the 
question is easier. If we have a sum of k consecutive odd numbers, 
starting at a, we have:

   N = a + (a + 2) + ... + (a + 2(k-1))
   N = k (a + k - 1)

If k >= 2 and a >= 1, both factors are >= 2, and this shows that N is 
not prime.

Note that, since a is odd, both factors have the same parity, and the 
second factor is greater that or equal to the first.

This means that there is no solution if N is a prime or twice a 
prime. If this is not the case, you can factor N as

  N = pq,

with p <= q and p = q (mod 2). In that case, you would set k = p and 
a = q + 1 - k (which is >= 1).

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 11/22/2006 at 00:55:28
From: Umair
Subject: proof

Please prove that an integer greater than 1 can be expressed as 
the sum of two or more consecutive positive integers if and only 
if it is not a power of 2. 

For example, 5 = 2+3, 10 = 1+2+3+4, 15 = 7+8 = 1+2+3+4+5 but no 
such expression can be found for 8, 16, 32 etc.

Date: 11/22/2006 at 04:14:49
From: Doctor Jacques
Subject: Re: proof

Hi Umair,

One proof can be found in an earlier answer to this question, shown
above.  However, after some additional thought, I believe that this
can be shown in a slightly simpler way.

The basic idea is still the same: by the formula for an arithmetic 
progression, the sum of k consecutive integers starting at 'a' is 
given by:

  n = k*(a+b)/2                [1]

where b = a + k - 1 is the last term.  Substituting into [1], we get:

  n = k * (2a + k - 1) / 2     [2]

Note that, if k is even, (2a + k - 1) is odd, and conversely.

In this case, n is the given number, and we must find k and a, where 
k is the number of terms and a is the first term.  We must have k > 1 
and a > 0.

If n is a power of 2, the odd factor must be 1.  It cannot be k, since 
we require k > 1, and we must therefore have:

  2a + k - 1 = 1
  2a + k = 2

Since a >= 1 and k >= 2, this is obviously impossible.

Let us now assume that n is not a power of 2.  This means that:

  n = 2^r * m                  [3]

where m is odd and > 1.

We can rewrite [2] as:

  2a = (2n/k) - k + 1          [4]

We must choose the integer k > 1 in such a way that a is a positive 
integer.  Looking at [4], we see that a is smaller if k is greater; 
this shows that, to ensure that a > 0, we should take k as small as 
possible.

We have 2n = 2^(r+1) * m.  There are two possible cases, depending on 
which of 2^(r+1) or m is the greater (note that we cannot have 
equality, since the former is even and the latter is odd).

Case 1 : m < 2^(r+1)
--------------------

In this case, we take k = m, giving:

  2a = 2^(r+1) - m + 1         [5]

We have a > 0, because m < 2^(r+1), and 2a is even, since m is odd, 
and a is therefore an integer.

An example of this case is n = 24 = 2^3 * 3.  We have r = 3 and m = 3. 
We take k = 3, and [5] gives:

  2a = 2^4 - 3 + 1
   a = 7

and we have indeed:

  24 = 7 + 8 + 9

Note that, as n is not a power of 2, k = m > 1, and we have indeed at 
least two terms.

Case 2 = m > 2^(r+1)
--------------------

In this case, as you might have guessed, we take k = 2^(r+1), giving:

  2a = m - 2^(r+1) + 1          [6]

and, using a similar argument as in the previous case, you can check 
that 2a is again an even positive integer.

For example, if n = 14, we have r = 1 and m = 7.  As m = 7 > 2^2 = 4, 
we take k = 4, and [6] gives:

  2a = 7 - 4 + 1
   a = 2

and we have indeed:

  14 = 2 + 3 + 4 + 5

The above procedure gives a "standard" solution - it will always work 
whenever n is not a power of 2.  However, there may be other solutions 
as well, if n has more than one odd divisor.

The idea behind [4] is that we must factorize 2n as the product of 
two factors, one odd and one even, and take k as the smaller of these 
factors.  For example, with n = 21, we may write:

  42 = 6*7 = 3*14 = 2*21

and this gives three solutions:

  k = 6, 2a = 2,  21 = 1 + 2 + 3 + 4 + 5 + 6
  k = 3, 2a = 12, 21 = 6 + 7 + 8
  k = 2, 2a = 20, 21 = 10 + 11

where the last solution is the one that you would have obtained using 
the "standard" procedure above (case 2).

Note that, if you try to apply the procedure when n is a power of 2, 
you would end in case 1 with k = m = 1, and this is not an acceptable 
solution, since we require k > 1.

Please feel free to write back if you want to discuss this further.
 
- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/