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=2k+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=mk. Then
n=k+k++km times
and since m is odd, say m=2l+1 we have
n=k+k++kl times+k+k+k++kl times

and we can start moving 1s one by one from the left side of the middle "k" to the right side of it
n=k+k++(k1)l times+k+(k+1)+k++kl times
n=k+k+(k2)+(k1)l times+k+(k+1)+(k+2)++kl 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=112. 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 1s 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
(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 2n. 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 cannot be expressed2m cannot be expressed
I am done. So I was trying to show the contrapositive

2m can be expressedm 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 2n 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 2n=k1i=0(m+i)=km+k(k1)2 for some k>1 and m>0, then 2n+1=2km+k(k1)=k(2m+k1). Note then that this implies that k=2 for some >0, and therefore that 2m+k1 is odd, and therefore that in fact, k=2n+1, and 2m+k1=1. Therefore we have 2m+2n+1=2, and m+2n=1, so m=12n0. Thus 2n 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 limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...