 mersenneforum.org An old puzzle for the new year
 Register FAQ Search Today's Posts Mark Forums Read  2021-01-04, 19:41 #1 Dr Sardonicus   Feb 2017 Nowhere 23×569 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?   2021-01-04, 20:00 #2 Uncwilly 6809 > 6502   """"""""""""""""""" Aug 2003 101×103 Posts 33×5×71 Posts 1 and the evens.   2021-01-04, 20:07   #3
bsquared

"Ben"
Feb 2007

D6E16 Posts The powers of 2

I don't have an elegant solution either - just starting writing down sums and observed a pattern.

Quote:
 Originally Posted by Uncwilly 1 and the evens.
The puzzles states two or more consecutive integers.   2021-01-04, 20:13   #4
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

33×5×71 Posts Quote:
 Originally Posted by bsquared The puzzles states two or more consecutive integers.
At least I was partially right.   2021-01-04, 20:50 #5 R. Gerbicz   "Robert Gerbicz" Oct 2005 Hungary 146810 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^u-2*k)/2 ; b1=2*k>0 a2=(2*k-2^u+2)/2 ; b2=2^u-1>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=(tmp-1)/2; a1=(2^u-2*k)/2;a2=(2*k-2^u+2)/2;if(a1>0,print(a1"+...+"a1+2*k),print(a2"+...+"a2+2^u-1))}   2021-01-04, 21:54 #6 charybdis   Apr 2020 2·7·19 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 (k-1)+(k-2)+....+(-(k-2))+(-(k-1)) 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.   2021-01-05, 00:12   #7
uau

Jan 2017

10110102 Posts Quote:
 Originally Posted by charybdis Not sure if this counts as elegant:
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.   2021-01-05, 03:18 #8 LaurV Romulan Interpreter   Jun 2011 Thailand 22×17×139 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.    2021-01-05, 07:03 #9 Citrix   Jun 2003 1,579 Posts Sum of n consecutive numbers==> (n / 2) *(first number + last number) = sum Last number=first number +n-1 n*(2*first number +n-1)-2*sum=0 first number =f n^2+(2*f-1)*n-2*sum=0 This is a quadratic equation. We want to find integer roots and positive solutions. This will have integer roots if (2*f-1)^2+8*sum=y^2 y will be odd as 2*f-1 is odd We also have n>=2 and y>=(2*f-1)+4 for positive solutions greater than 2 or y-(2*f-1)>=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*f-1)^2=8*sum (y-(2*f-1)) * (y+(2*f-1)) = 8*sum Both (y-(2*f-1)) & (y+(2*f-1)) will be even Both (y-(2*f-1)) & (y+(2*f-1)) cannot be 0 (mod 4) otherwise y and 2f-1 will be even For odd y and (2*f-1) 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^(x-1) in accordance with concept 2 then y=2^(x-2)+1 and (2*f-1)=2^(x-2)-1 But y-(2*f-1)>=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 2021-01-05 at 07:09   2021-01-06, 15:17 #10 Dr Sardonicus   Feb 2017 Nowhere 23·569 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. Ta-daaaah! 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 non-positive 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 -(s-1) to s. A negative integer s is the sum of the integers from s to -s-1. Last fiddled with by Dr Sardonicus on 2021-01-06 at 17:59 Reason: xigfin posty   2021-01-07, 05:02 #11 LaurV Romulan Interpreter   Jun 2011 Thailand 945210 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 2021-01-07 at 05:07   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Mark Rose Tales From the Crypt(o) 50 2019-06-24 07:05 tcharron Information & Answers 8 2014-01-29 20:16 petrw1 Factoring 3 2013-03-20 19:34 bdodson GMP-ECM 142 2013-03-01 12:54 QuintLeo Lounge 14 2003-11-14 07:56

All times are UTC. The time now is 05:39.

Tue May 18 05:39:29 UTC 2021 up 40 days, 20 mins, 0 users, load averages: 1.77, 1.85, 1.98