An old puzzle for the new year

[Dr Sardonicus]

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?

[Uncwilly]

1 and the evens.

[bsquared]

The powers of 2

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

Originally Posted by Uncwilly

1 and the evens.

The puzzles states two or more consecutive integers.

[Uncwilly]

Originally Posted by bsquared

The puzzles states two or more consecutive integers.

At least I was partially right.

[R. Gerbicz]

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))}

[charybdis]

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.

[uau]

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.

[LaurV]

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.

[Citrix]

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

[Dr Sardonicus]

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.

[LaurV]

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).