Which positive integers can NOT be written as a sum of consecutive positive integers

Question

I have been wondering about this question for a while (I am almost sure that I read it in some contest mathematics book a while ago)

Determine which positive integers cannot be written as a sum of consecutive positive integers.

All numbers will be considered positive integers in the following unless stated otherwise.

I was thinking as follows: odd numbers will always work since if we take an odd $m$, we have

$$ m=2\cdot k+1=k+(k+1). $$

Then I realised that all numbers having at least one odd prime factor will also work. Take $n$ as a number having an odd prime factor and let this odd prime factor be $m$ and let $n=m\cdot k$. Then $$ n=\underbrace{k+k+\ldots+k}_{m \ \text{times}} $$ and since $m$ is odd, say $m=2\cdot l+1$ we have $$ n=\underbrace{k+k+\ldots+k}_{l \ \text{times}}+k+\underbrace{k+k+\ldots+k}_{l \ \text{times}} $$ and we can start moving $1$s one by one from the left side of the middle "$k$" to the right side of it $$ n=\underbrace{k+k+\ldots+(k-1)}_{l \ \text{times}}+k+\underbrace{(k+1)+k+\ldots+k}_{l \ \text{times}} $$ $$ n=\underbrace{k+k+\ldots(k-2)+(k-1)}_{l \ \text{times}}+k+\underbrace{(k+1)+(k+2)+\ldots+k}_{l \ \text{times}} $$ this way we end up in a sum of consecutive integers. It may happen that some integers on the left will be negative which is undesired but since these numbers are consecutive integers we always be able to cancel out the negative ones without disturbing the structure of the uncancelled ones. To see this in action let us take $22=11\cdot 2$. This would give $$ 2+2+2+2+2+2+2+2+2+2+2 $$ so $$ 2+2+2+2+1+2+3+2+2+2+2 $$ the next step gives $$ 2+2+2+0+1+2+3+4+2+2+2 $$ it seems that now we are out of numbers but we just continue moving an increasing number of $1$s to the right $$ 2+2+(-1)+0+1+2+3+4+5+2+2 $$ $$ 2+(-2)+(-1)+0+1+2+3+4+5+6+2 $$ finally $$ \underbrace{(-3)+(-2)+(-1)+0+1+2+3}_{=0}+4+5+6+7 $$ so we get $$ 22=4+5+6+7. $$

Now we have a method to generate the desired expression for all odd numbers and all the ones having at least one odd prime factor. Which numbers are left? The ones having ONLY even primes in their prime factorisation. These are of the form $2^n$. I was thinking what do these have in common and I thought that they are separated by a factor of $2$. The first of these are $1$ for $n=0$ and $1$ cannot be expressed in the desired for so if I could show that $$ m \ \text{cannot be expressed}\Rightarrow 2m \ \text{cannot be expressed} $$ I am done. So I was trying to show the contrapositive $$ 2m \ \text{can be expressed}\Rightarrow m \ \text{can be expressed}. $$ So assume that $2m$ can be expressed. Now, eihter $m$ is odd in which case we are done since odds were easy to express or it is even, that is $m=2l$. From here the argument repeats. Eihter $l$ is odd in which case we are done or it is even, so $l=2k$ and so on. After a while we factored out all of the $2$'s and we end up with and odd number which we can express and we are done.

So integers of the form $2^n$ cannot be expressed in this form.

Is my reasoning correct?

If not please point out where I made a mistake. If it turns out to be correct then we are all happy I can sleep well tonight but it would be nice to see a more rigorous proof of this so if someone can provide one I am more than happy to read it. Since this is a contest question I expect it to have a really elegant solution and I do not consider mine an elegant one.

Answer 1

Suppose $$2^n = \sum_{i=0}^{k-1} (m+i) = km + \frac{k(k-1)}{2}$$ for some $k>1$ and $m>0$, then $2^{n+1}=2km+k(k-1)=k(2m+k-1)$. Note then that this implies that $k=2^\ell$ for some $\ell > 0$, and therefore that $2m+k-1$ is odd, and therefore that in fact, $k=2^{n+1}$, and $2m+k-1=1$. Therefore we have $2m+2^{n+1}=2$, and $m+2^n = 1$, so $m=1-2^n\le 0$. Thus $2^n$ is not expressible as a sum of consecutive positive integers.

Edit:

I realized I posted this answer without really addressing the actual question, although I sort of answered in the comments. Everything other than the argument to show that powers of $2$ can't be expressed looked ok to me. I didn't follow your argument for the powers of $2$, which is why I wrote this answer.

Answer 2

Yes, I think your reasoning is correct. I have also given a solution below.

Let's consider sum of $r$ consecutive positive integers with first term $a$ and last term $l$. Since the integers are consecutive thus the terms are in Arithmetic Progession and thus we can apply formula related to AP. Sum of AP is number of terms into its mean, where mean of whole arithmetic series is equal to mean of first and last term.

Sum of consecutive terms $=$ $r*(a+l)/2$ where $r>1$.
$Case 1$
If the number of terms($r$) is odd then we already have a odd factor in the sum. Please note that both $a$ and $l$ will have same parity, thus mean $(a+l)/2$ will be an integer.
$Case 2$
If number of terms($r$) is even then we can say that parity of $a$ and $l$ will be different, i.e., if $a$ is even then $l$ will be odd and vice-versa. Thus the sum will have an odd factor as $a+l$. Since we are talking about postive integers thus ${a+l}>1$. Here $r/2$ will be integer.

Both cases show that sum of positive consecutive integers will always have an odd factor in it. So sum of positive consecutive integers can only represent numbers having at least one odd factor, say $m$, which is $>1$.

Now to show that all positive integers of form $n = 2^{p}*m$, where $m>1$ is odd number, can be expressed as sum of consecutive integers. We can see two cases. We will use the fact that sum of consecutive numbers is number of terms into its mean.
$Case 1$ : $m>2^{p+1}$
Here the idea will be to take $2^{p+1}$ consecutive numbers with mean of numbers as $m/2$. Please note that $m/2$ is not an integer. So we will take equal number of integers from left and right side of $m/2$ on the number line till we get a total of $2^{p+1}$terms.
$Case 2$ : $m<2^{p+1}$
Here the idea will be to take $m$ consecutive numbers with mean of numbers as $2^{p}$. So starting form $2^p - ((m-1)/2)$ we will take all consecutive numbers till $2^p + ((m-1)/2)$