mersenneforum.org An old puzzle for the new year
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-01-04, 19:41 #1 Dr Sardonicus     Feb 2017 Nowhere 2·3·971 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 22×3×883 Posts 1 and the evens.
2021-01-04, 20:07   #3
bsquared

"Ben"
Feb 2007

70438 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

22·3·883 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 110001001012 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 74810 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

2·73 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     "name field" Jun 2011 Thailand 233658 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 110001101002 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 2×3×971 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     "name field" Jun 2011 Thailand 9,973 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

 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 14:11.

Mon Jun 27 14:11:43 UTC 2022 up 74 days, 12:13, 2 users, load averages: 0.88, 1.12, 1.18

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔