20210104, 19:41  #1 
Feb 2017
Nowhere
4447_{10} Posts 
An old puzzle for the new year
The following problem is not difficult. Any Forumite should be able to determine the answer. I don't know any really elegant solution. The answer seems curious to me, but I am not aware of it being anything more than a curiosity.
Which positive integers can not be expressed as the sum of two or more consecutive positive integers? 
20210104, 20:00  #2 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
2×7×677 Posts 
1 and the evens.

20210104, 20:07  #3 
"Ben"
Feb 2007
3403_{10} Posts 

20210104, 20:13  #4 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
9478_{10} Posts 

20210104, 20:50  #5 
"Robert Gerbicz"
Oct 2005
Hungary
2×727 Posts 
We need for a given x>0 that x=a+..+(a+b)=(2*a+b)*(b+1)/2 with a,b>0 So: 2*x=(2*a+b)*(b+1) Notice that 2*a+b and b+1 has different parity, hence if x is a power of two then this equation has no solution [because 2*a+b>1 and b+1>1 and of them is odd]. Let 2*x=2^u*(2*k+1) with u>0 and k>0 (because x is not power of two). Even there could be lots of such decompositions of 2*x to (2*a+b)*(b+1) we can regard only one of them and its pair to get a "good" solution: 2*x=2^u * (2*k+1) 2*x=(2*k+1) * 2^u solving this: a1=(2^u2*k)/2 ; b1=2*k>0 a2=(2*k2^u+2)/2 ; b2=2^u1>0 notice that a1+a2=1 so one will be a good solution, giving a1>0 or a2>0. In code [if x is a power of two then it will return the fake trivial solution]. F(x)={tmp=2*x;u=0;while(tmp%2==0,u+=1;tmp/=2);k=(tmp1)/2; a1=(2^u2*k)/2;a2=(2*k2^u+2)/2;if(a1>0,print(a1"+...+"a1+2*k),print(a2"+...+"a2+2^u1))} 
20210104, 21:54  #6 
Apr 2020
223 Posts 
Not sure if this counts as elegant:
Suppose n = ab where b>1 is odd. Then when we write n = a+...+a, one of the a's is in the middle, so we can easily rewrite this as a sum of consecutive integers, eg 7+7+7+7+7 becomes 9+8+7+6+5; the sums are the same because 9+5 = 7+7 etc. If the resulting sum contains negative numbers, that isn't a problem because they just cancel out the smallest positive numbers, eg 14 = 2+2+2+2+2+2+2 = 5+4+3+2+1+0+(1) = 5+4+3+2. We can also run the above process in reverse to go from an expression of n as a sum of consecutive positive integers to an odd factor of n. If the sum contains an odd number of terms, then n = (number of terms)*(middle term). If it contains an even number of terms, then if k is the smallest term in the sum, we can add (k1)+(k2)+....+((k2))+((k1)) to get a new sum with an odd number of terms. Some of these terms are negative but that doesn't matter. The only numbers without nontrivial odd factors are the powers of 2, so we're done. 
20210105, 00:12  #7 
Jan 2017
2^{3}·11 Posts 
The cancellation trick is nice and gives a short solution to most of the problem. I think the other case is a bit simpler without reducing to that though:
That is, the sum is always the mean of the numbers times their count. If the count is odd, the mean is an integer. If it's even, the mean is m+1/2, and the product is divisible by 2m+1. 
20210105, 03:18  #8 
Romulan Interpreter
Jun 2011
Thailand
2497_{16} Posts 
We inadvertently put the mouse on bb's spoiler and spoiled all the fun...
But we read the answers and consider that if we put all together and cut out complicate parts, you all solved the puzzle in an elegant way. 
20210105, 07:03  #9 
Jun 2003
1,579 Posts 
Sum of n consecutive numbers==> (n / 2) *(first number + last number) = sum Last number=first number +n1 n*(2*first number +n1)2*sum=0 first number =f n^2+(2*f1)*n2*sum=0 This is a quadratic equation. We want to find integer roots and positive solutions. This will have integer roots if (2*f1)^2+8*sum=y^2 y will be odd as 2*f1 is odd We also have n>=2 and y>=(2*f1)+4 for positive solutions greater than 2 or y(2*f1)>=4  Concept 1 Or 8*sum needs to be a difference of 2 odd squares; with each even factor pair giving a unique solution. y^2(2*f1)^2=8*sum (y(2*f1)) * (y+(2*f1)) = 8*sum Both (y(2*f1)) & (y+(2*f1)) will be even Both (y(2*f1)) & (y+(2*f1)) cannot be 0 (mod 4) otherwise y and 2f1 will be even For odd y and (2*f1) only solution would be one of the set of factors1 =2 (mod 4) and other factors2=0 (mod 4)  Concept 2 If sum is a power of 2; 8*sum=2^x with only factors =2 and 2^(x1) in accordance with concept 2 then y=2^(x2)+1 and (2*f1)=2^(x2)1 But y(2*f1)>=4 so there is no solution for powers of 2 Combining concept 1 and 2 For all other values of sum; 8*sum can be factored into a solution where the smaller factor >=4 and one of the factors =2 (mod 4) and other factor=0 (mod 4) For all other values, other than powers of base 2, their will be a solution as explained above Simpler solution from google https://nrich.maths.org/summingconsecutive/solution Last fiddled with by Citrix on 20210105 at 07:09 
20210106, 15:17  #10 
Feb 2017
Nowhere
4,447 Posts 
Here's my solution  considerably refined, thanks to the postings to this thread!
I believe what I first saw about this curiosity was the assertion that any positive integer could be expressed as a sum of two or more consecutive integers, unless it was a power of 2. This, of course, was a great advantage in analyzing the situation, since I already knew what was true, and only needed to determine why it was true. The obvious commonality of positive integers that are not powers of two is, they have an odd factor greater than 1. So the obvious thing to look for was an algebraic factorization of a sum of consecutive integers. It occurred to me that a sum of consecutive integers is the difference of two triangular numbers. And I knew that "8*triangle plus 1 = square," so a factorization as a difference of two squares was in sight. s = Tm  Tn with m  n > 1 8*s = 8*Tm  8*Tn = (8*Tm + 1)  (8*Tn + 1) = (2*m + 1)^2  (2*n + 1)^2 8*s = (2*m  2*n)*(2*m + 2*n + 2) 2*s = (m  n)*(m + n + 1) where, again, m  n > 1 Both algebraic factors of 2*s are greater than 1 by hypothesis, and the difference of the two factors is 2*n + 1, an odd number, so one of the factors is an odd number greater than 1. Obviously, given a positive integer s, the factorizations of 2*s as above which produce m and n with m  n > 1, correspond exactly to the odd divisors d > 1 of s, and the cofactor 2*s/d of 2*s. Tadaaaah! One irksome thing about this analysis is that Tm  Tn is the sum of the m  n integers from n+1 to m, not the integers from n to m. It is also less "elegant" than the "trapezoidal" factorizations of a sum of consecutive integers. One satisfying thing is, in the difference of two squares above, both squares are odd. It is this fact that leads to the algebraic factors of 2*s differing by an odd number (the smaller odd root). One pitfall of allowing nonpositive integers is, it allows ANY integer to be expressed as a sum of two or more consecutive integers. Zero is the sum of the integers from k to k for any k > 0. Any positive integer s can be expressed as the sum of the integers from (s1) to s. A negative integer s is the sum of the integers from s to s1. Last fiddled with by Dr Sardonicus on 20210106 at 17:59 Reason: xigfin posty 
20210107, 05:02  #11 
Romulan Interpreter
Jun 2011
Thailand
17·19·29 Posts 
If n contains no odd factor, Robert gave the demonstration why it can't be written as so.
If n contains an odd factor, charybdis gave the simplest algorithm to write it so. (edit: Robert also solved this, but charybdis' proof is simpler and constructive). The rest are complications (and only partially solve the problem, you all show how to write n if it have odd factors, but nobody except Robert show that no power of two can be written so. Maybe there are some HIGH powers of two which could be accidentally written so, therefore the second half of the proof is important too). Last fiddled with by LaurV on 20210107 at 05:07 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
20yearold MIT LCS35 Time Capsule CryptoPuzzle solved  Mark Rose  Tales From the Crypt(o)  50  20190624 07:05 
It's been a year  tcharron  Information & Answers  8  20140129 20:16 
Year Over Year TF Progress  petrw1  Factoring  3  20130320 19:34 
Top 10 GMPECM for the year  bdodson  GMPECM  142  20130301 12:54 
1 Year  QuintLeo  Lounge  14  20031114 07:56 