Thursday 13 August 2015

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



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



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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...