Powers of 2 ProofDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/