14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ jstor.org/stable/30215349?seq=1#metadata_info_tab_contents $\endgroup$ – vadim123 Feb 23 at 0:10
  • $\begingroup$ I don't at all understand your argument for why $2m$ being expressible implies $m$ is expressible. It seems like your argument is: Let $m=2^ko$ for $o$ odd. Then since $o$ is odd, $m$ is expressible, but this fails when $o$ is $1$, which is exactly the case you're trying to address. $\endgroup$ – jgon Feb 23 at 0:10
  • $\begingroup$ @jgon If $o$ is one then we are in the case $m=2^k$ which is the only case this way of expressing positive integers fails which is what I try to show. $\endgroup$ – Vinyl_cape_jawa Feb 23 at 0:13
  • $\begingroup$ @Vinyl_coat_jawa That's sort of my point, you're not proving what you want to prove. You're just reasserting that if $m$ isn't a power of $2$, then it is expressible. $\endgroup$ – jgon Feb 23 at 0:15
  • 2
    $\begingroup$ You may wish to check the similar Forming natural numbers with positive consecutive integers which starts with "I'm trying to prove that any natural number N can be formed by adding at least two positive consecutive integers except for powers of $2$.". Note it has $2$ answers which should help you. $\endgroup$ – John Omielan Feb 23 at 0:18
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.