mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2021-01-04, 19:41   #1
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·7·11·29 Posts
Default 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?
Dr Sardonicus is offline   Reply With Quote
Old 2021-01-04, 20:00   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2·5·13·73 Posts
Default

1 and the evens.
Uncwilly is offline   Reply With Quote
Old 2021-01-04, 20:07   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22×23×37 Posts
Default

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 View Post
1 and the evens.
The puzzles states two or more consecutive integers.
bsquared is offline   Reply With Quote
Old 2021-01-04, 20:13   #4
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

2×5×13×73 Posts
Default

Quote:
Originally Posted by bsquared View Post
The puzzles states two or more consecutive integers.
At least I was partially right.
Uncwilly is offline   Reply With Quote
Old 2021-01-04, 20:50   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

145810 Posts
Default


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))}
R. Gerbicz is offline   Reply With Quote
Old 2021-01-04, 21:54   #6
charybdis
 
Apr 2020

E616 Posts
Default

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.
charybdis is offline   Reply With Quote
Old 2021-01-05, 00:12   #7
uau
 
Jan 2017

23·11 Posts
Default

Quote:
Originally Posted by charybdis View Post
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.
uau is offline   Reply With Quote
Old 2021-01-05, 03:18   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

222418 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2021-01-05, 07:03   #9
Citrix
 
Citrix's Avatar
 
Jun 2003

1,579 Posts
Default



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
Citrix is offline   Reply With Quote
Old 2021-01-06, 15:17   #10
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·7·11·29 Posts
Default

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
Dr Sardonicus is offline   Reply With Quote
Old 2021-01-07, 05:02   #11
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

9,377 Posts
Default

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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
20-year-old MIT LCS35 Time Capsule Crypto-Puzzle solved Mark Rose Tales From the Crypt(o) 50 2019-06-24 07:05
It's been a year tcharron Information & Answers 8 2014-01-29 20:16
Year Over Year TF Progress petrw1 Factoring 3 2013-03-20 19:34
Top 10 GMP-ECM for the year bdodson GMP-ECM 142 2013-03-01 12:54
1 Year QuintLeo Lounge 14 2003-11-14 07:56

All times are UTC. The time now is 11:29.

Sun Apr 18 11:29:53 UTC 2021 up 10 days, 6:10, 0 users, load averages: 2.19, 2.21, 2.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.