Consecutive Positive Integers

Let $n$ be a positive integer. Suppose $n=a+(a+1)+...+(a+k)$ , where $a, k$ are positive integers. We claim that $n$ can be written in this form if and only if $n$ is not a power of 2.

Note that $a+(a+1)+...+(a+k)=\frac{ (2a+k)(k+1)}{2}$ . Note that $2a + k$ and $k + 1$ are of opposite parity. Thus, their product is not a power of 2, since they're both greater than 1. Thus, $n$ is not a power of 2.

Now we claim the converse. Suppose $n$ is not a power of 2. Write $n=2^rs$ , where $s$ is an odd integer greater than 1 (since $n$ is not a power of 2).
If $2^{r+1} > s$ , then let $k = s - 1, a = \frac{ 2^{r+1} - (s - 1)} {2}$ are positive integers. Then $\frac{ (2a+k)(k+1)}{2} =\frac { ( 2^{r+1}) (s) } {2} = n$ , hence satisfies the conditions.
If $2^{r+1} < s$ , then $k = 2^{r+1}-1, a = \frac{ s -(2^{r+1} -1) } { 2}$ are positive integers. Then $\frac{ (2a+k)(k+1)}{2} =\frac { (s) (2^{r+1}) } {2} = n$ , hence satisfies the conditions.

Since there are 10 powers of 2 less than or equal to 1000, so the answer is $1000-10=990$ .

Solution: Note that all odd positive integers, n, greater than 1 satisfy the property since n=(n/2+1/2)+(n/2-1/2). Note, I claim that if n has both an odd factor and an even factor, then the property holds as well. Let n=a*b where a is odd and b is a power of 2 and both a,b>1.

If b<= n/2-1/2, then we take the sequence {n/2+1/2-b, n/2+3/2-b, ..., n/2-1/2+b} of 2b integers. Therefore, all values of n in this case satisfy the given condition. If b>n/2-1/2, then take the sequence {b-(n-1)/2, b-(n-1)/2+1, ..., b+(n-1)/2} of n positive integers. Again, all values of n in this case satisfy the given condition. Now, the only case left to consider is where n is a power of 2. Clearly, if k is odd, then the sum of the sequence is a multiple of k, so this cannot be the case. Also, if k is even, then the total sum is an odd number, so this cannot be the case either. We conclude that the only values of n that do not satisfy the given condition are powers of 2, i.e. 1, 2, 4, 8, ... There are 10 such powers of 2 under 1000, so our answer is 1000-10=990.

The first observation we can make, in the attempt to solve the problem, is that the numbers $1$ and $2$ cannot be expressed as the required sum, $3$ can, and again $4$ cannot, while $5$ can, and so on.

(In fact the easiest numbers to be decomposed as the sum of n terms are the odd ones: any odd number other than $1$ can be expressed as 2q + 1, with q positive integer: 2q + 1 = q + (q + 1).

Now, observing that $1 = 2^0$ we are led to the result below...)

Generalizing this, the sum of $n$ consecutive integers from $m$ to $m + n - 1$ is $S = \frac{\left(\left(2m - 1\right) + n\right)n}{2}$ .

If S is a power of 2, say $S = 2^x$ we have immediately a problem, since $2^{x+1} = \left(\left(2m - 1\right) + n\right)n$ , which cannot be satisfied by any integer $m$ : either n is even, and the first factor on the right-hand-side is odd $n$ itself is odd (which means that there is a factor other than $2$ , in contradiction with the assumption).

Hence, no power of two can be expressed as the sum of two or more consecutive positive integers.

Can all other positive integers be expressed as the said sum? Yes! In fact, any positive integer, can be written as: $2^x \left(2s + 1\right)$ , with $x, s \in \mathbb{N}$ (including $0$ , with $x = 0$ we obtain all odd numbers). Therefore we have: $S = \frac{2^{x+1}(2s + 1)}{2}$ , and that's it: we just need to find $2s + 1$ terms whose sum is $2^{x+1}$ or $2^{x+1}$ terms whose sum is $2s + 1$ .

Hence the second-last step is proving that the numbers $S$ of the form $S = \frac{2^{x+1}(2s + 1)}{2}$ are sum of consecutive terms, namely: $2^{x+1}(2s + 1) = \left(\left(2m - 1\right) + n\right)n$ .

Let $n$ be odd: $2^{x+1}(2s + 1) = 2p (2r + 1)$ , hence $p = 2^x$ and $r = s$ . Let $n$ be even: $2^{x+1}(2s + 1) = (2t + 1) 2w$ , hence $t = s$ and $w = 2^x$ . (Here is meant that $p, r, t,$ and $w$ are integers.).

The problem therefore reduces to count how many powers of $2$ there are between 1 and 1000 (included): $512 = 2^9$ is the highest power $\le 1000$ , and there are ten in total. The required number is therefore $1000 - 10 = 990$ .

I knew I couldn't do this problem out longhand, so I started looking for patterns. I knew that all odd numbers could be written as the sum $\lfloor \frac{x}{2} \rfloor + \lceil \frac{x}{2} \rceil$ . (Since we were only looking at positive integers, that doesn't solve for 1, but it solves all other odd numbers.)

Next I decided to look for solutions to multiples of 3. (I got this idea from the hint: 9=2+3+4.) I saw this as another pattern. For a multiple of 3, we can use $(\frac{x}{3}-1) + \frac{x}{3} + (\frac{x}{3}+1)$ .

Maybe this pattern continues for other odd numbers: I tried 5. I found that for a multiple of 5, I could use $(\frac{x}{5}-2)+(\frac{x}{5}-1)+\frac{x}{5}+(\frac{x}{5}+1)+(\frac{x}{5}+2)$ .

If it works for 3 and 5, I figured it would continue to work for more odd numbers. The general form (for a multiple of odd number n) being the sum of n numbers centered on $frac{x}{n}$ .

Now I had all of the odd numbers plus all of the even numbers that had an odd factor. However, a problem remained for the numbers without an odd factor. There's a pattern for these as well: these are the powers of 2. I tried testing a few of the smaller powers of 2 and realized I was never going to find a solution for them. So that gave me the answer. I could find solution for all numbers that were not powers of 2. The powers of 2 less than 1000 are ${1,2,4,8,16,32,64,128,256,512}$ . There are 10 of them, so the answer to the problem is $1000-10=990$ .

Every number except 2^n where n could be 0,1,2,3....... can be expressed as the sum of consecutive positive integers. Suppose the k numbers are n + 1, n + 2, ..., n + k Sum = k(k + 2n + 1)/2 Now one of k and (k + 2n + 1) will be odd and both k and (k + 2n + 1) are greater than 2 (as k > 2) => Sum should have atleast one odd factor greater than 1 Only numbers which doesn't have any odd factor greater than 1 are of form 2^n Hence, 1000-10=990 terms (10 terms = 2^0, 2^1....up to 2^9)

First note that every odd number > 1 can be decomposed into 2 consecutive positive integers. Odd numbers are defined as n = 2k+1, hence k + (k+1) is a solution for every odd number > 1.

Next, note that every even number can be decomposed into its prime factors. For example, 20 = 2^2 * 5. Also note that 2 is the only even prime.

Hence, for all n that are not powers of 2, there is an odd prime factor.These numbers are thus n=2^a b c ..., where b,c,... are odd prime factors and b is the smallest odd prime factor. Thus a solution for n can be written as (2^a c ...-((b-1)/2))+(2^a c ...-((b-1)/2)+1)+...+(2^a c ...+((b-1)/2)). E.g. 20 = 2^2 * 5, hence can be written as 2+3+4+5+6 = 8 5/2 = 20.

Thus, the only numbers that cannot be expressed as such are the powers of 2, i.e. 1,2,4,8,...,256,512. There are 10 such powers <=1000, hence the number of possible such numbers = 1000-10=990

All the odd numbers, except for 1, can be expressed as the sum of two consecutive numbers. Thus, we only need to check the even numbers. 2 and 4 can't be expressed as the sum of consecutive numbers since 1 + 2 + 3 = 6. So 6 is the smallest even number which can be expressed as the sum of consecutive numbers. Let's list out a few more to find the pattern. You can express 10 as 1 + 2 + 3 + 4, 12 = 3 + 4 + 5, 14 = 2 + 3 + 4 + 5, You can not express 16, 18 = 5 + 6 + 7.

From here, we can see that you can't express number 2, 4, 8, 16. So it can be concluded that every power of two can not be expressed as the sum of consecutive numbers. Since 2^9 = 512 and 2^10 = 1024, there are 9 numbers which can't be expressed as the sum of consecutive numbers. Hence, there are a total of 10 numbers (including number 1) Therefore there are 1000 - 10 = 990 numbers from 1 to 1000 which can be expressed as the sum of consecutive numbers.

---

Alternatively, you can use average method to solve this. For all odd numbers, except number 1, it can be expressed as the sum of two consecutive numbers. For even numbers which is also a multiple of 3, it can be expressed as the sum of 3 consecutive numbers. For even numbers which is also a multiple of 5, it can be expressed as the sum of 5 consecutive numbers. In conclusion, for a prime number k (except 2), all even numbers which is also a multiple of k, it can be expressed as the sum of k consecutive numbers. Therefore, the only one that can't be expressed by consecutive numbers is the power of 2 (i.e. 2, 4, 8, ...)

Suppose $n = a_1 + a_2 + \ldots + a_k$ . Then we can also write $n = \frac{(a_1 + a_k)k}{2} = \frac{(2a_1 + k - 1)k}{2}$ , and so $2n = (2a_1 + k - 1)(k).$ We can factor $2n = 2^mp$ where $p$ is odd and $m\geq 1$ . Observe that $(2a_1 + k-1)$ and $k$ have different parity.

If $p \geq 3$ and $2^m > p$ , then let $2a_1 + k-1 = 2^m, k=p$ , which will have positive integer solutions for $(a_1, k)$ and $k \geq 2$ . If $p\geq 3$ and $2^m < p$ , then let $2a_1 + k - 1 = p, k = 2^m$ , which will have positive integer solutions for $(a_1, k)$ and $k \geq 2$ .

Claim: When $p = 1,$ (i.e. $n = 2^m, m\geq 1$ ), then we cannot find values of $a_1,k$ that will work.
Since the quantities $2a_1+k-1$ and $k$ have different parity, so one would have to be $2^m$ and the other is $p = 1$ . If $k = 1$ , we have a contradiction. When $k = 2^m$ , we clearly do not have $2^m$ consecutive positive integers which sum to $2^m$ .

Thus, all numbers except those which are powers of 2 can be expressed as the sum of at least 2 consecutive integers. There are 10 numbers which are powers of 2, which are $1,2,4,8,16,32,64,128,256,512$ , so there are 990 numbers which can be expressed in the desired way.