Edit: The bit about the larger prime numbers was due to an error in my VBA programming, but it lead to a better understanding of the problem. Don’t take this article as “final”, is the point.
This week’s puzzle in my Mathematics Reasoning class:
Try to express positive integers in terms of the sum of two or more consecutive positive integers. For instance, 3 = 1+2, 9 = 2+3+4, and so on. For which numbers 1 to 25 is it possible to do this?
I’ll leave the reader to solve the actual puzzle; it’s fun, and good for you. I want to focus on the exceptions.
One of my fellow students noticed the first part of the exceptions: It doesn’t work for 1, 2, 4, 8, and 16, which is exactly the set of powers of 2 for that range. That is, \[2^0 = 1,\,2^1 = 2,\,2^2 = 4,\, 2^3 = 8,\, 2^4=16\] This is the complete set of exceptions for the numbers 1 to 25, but it raises two questions:
- Are there solutions for any power of 2?
- Are all exceptions powers of 2?
I explored an algebraic solution, but haven’t yet found a solution to the first question (or rather, a proof that no solution exists for any power of two). So I tried brute force in Excel by looking at all values 1 to 100,000. For that range, I have answers to both questions.
It is indeed the case that it is not possible to express any power of 2 (up to 65,536) in terms of a sum of two or more consecutive positive integers. I tried sequences of up to 450 numbers (\(\sum\limits_{i=1}^{450} i = 101,475\)), and no solutions were found.
However, there are other exceptions as well. The lowest number which is not either a power of two or the sum of two or more consecutive positive integers is 368. The first ten numbers in this series are 368, 464, 496, 592, 656, 688, 736, 752, 848, and 928.
At first I didn’t see a series, then I noticed these are all multiples of 16; in fact, divide by 16 and we’re left with consecutive prime numbers, with two exceptions: 23, 29, 31, 37, 41, 43, (46), 47, 53, (58). That is, 368 = 23 • 16, 464 = 39 • 16, and so on. Those two exceptions? 736 = 23 • 32 and 848 = 29 • 32.
This lead me to a new series: All numbers which are primes greater than or equal to 23 (let’s call this set P23) multiplied by 2 to a power 4 or higher (let’s call this set S2^4) are exceptions. 1472 (23 • 32)? Exception. 4736 (37 • 128)? Exception.
However, even that doesn’t cover all the exceptions. I was double-checking to make sure that all the exceptions were indeed primes (times a member of S2^4) when I ran across 8,464 (529 • 16). It’s a multiple of 16, but 529 isn’t prime. However, 529 is a product of members of P23 (specifically, 23 • 23).
As I continued my checking, I found that every number from 1 to 100,000 that can’t be expressed in terms of two or more consecutive positive integers can be expressed in one of these forms:
- A power of 2
- A member of P23 times a member of S2^4
- A member of P23 times a member of P23 times a member of S2^4
The first number which is the product of three members of P23 and a member of S2^4 is 194,672 (23 • 23 • 23 • 16), which likewise has no solutions. Based on this, an obvious hypothesis for all positive integers is:
- A positive integer I can be expressed in terms of two or more consecutive integers if and only if it cannot be expressed as (where n and m are positive integers):
- 2n
- P231 • .. • P23m • 24+n
or, in more natural language, a positive integer is either:
- The sum of some set of consecutive positive integers,
- A power of two,
- Or a power of two greater than 8 times one or more primes greater than 19.
These three sets are mutually exclusive.
I don’t know what’s so special about P23; that is, why does the pattern not emerge at some lower prime, and why does it not skip primes once established? It’s possible there are exceptions to this hypothesis, greater than 100,000; I honestly don’t know if this is a number theory problem with an established literature and proof, or just another mathematical curiosity.
Edit:
I’ve been given a nudge elsewhere on the appropriate proof for powers of 2.
I posted that proof on Google+ before you added it here, but I’m not sure if you got the nudge through there or someone else. Anyway, there seems to be another problem:
The lowest number which is not either a power of two or the sum of two or more consecutive positive integers cannot be 368 because it equals 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28. Also the rest of the numbers you have in that series seem wrong, so you might need to check… you have some systematic error there.
368 = 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27
8464 = 249 + 250 + 251 + 252 + 253 + 254 + 255 + 256 + 257 + 258 + 259 + 260 + 261 + 262 + 263 + 264 + 265 + 266 + 267 + 268 + 269 + 270 + 271 + 272 + 273 + 274 + 275 + 276 + 277 + 278 + 279 + 280
Although I confirm your sequence if we restrict the sum to be 20 or fewer numbers (both of these are more than 20 numbers). This is still an interesting sequence involving primes… I wonder why.
Interesting bit with the powers of two, though. I think those are the only real exception, but I don’t yet have a proof.
I think you’ve pinpointed where I made my programming error. Unfortunately, I failed to save the actual code, but I may well have limited the sum loop to 20.
I think I’ve got it, but I need to formalize it.
Let P be the lowest odd prime factor of S, a given integer. Let 2^N be the highest power of 2 that divides S. If 2*2^N < P, then there exists a sum of 2*2^N integers. If P < 2*2^N, then there exists a sum of P integers.
This is why my mistaken pattern involves 16*23 but not 8*23: 8*2 23, so the shortest solution for 16*23 is 23 values long.
Proof:
http://herosgarden.com/blog/sums-of-positive-consecutive-integers-proof/
Let me formulate the problem thinking like a programmer:
A series of N consecutive integers is N/2 equal pairs of the first and the last member of that series. When N is odd, then the integer in the middle is a lone exception that equals half of the value of the other pairs.
Let’s say that the number of pairs M = N/2. The number of pairs M can include halves as explained above.
Let’s say P is the sum of the first and the last integer of the series, so P is the value of the pairs.
Now, the sum of the whole series is S = P * M.
With the simplest series M = 1 and P = 3, so S = 3.
Shrinking or growing N one step lower or higher, either substracts or adds 1 to the value of the pairs (P +/- 1) that make up the series at the same time removing or adding a half pair (M +/- 0.5).
So, the operations in pseudo code are:
Shrink to left (remove last member):
Boundary condition: M > 1
P := P – 1
M := M – 0.5
Shrink to right (remove first member):
Boundary condition: M > 1
P := P + 1
M := M – 0.5
Grow to left (add new first member):
Boundary condition: P > 2*M + 1
P := P – 1
M := M + 0.5
Grow to right (add new last member):
Unbounded
P := P + 1
M := M + 0.5
Moving the series lower or higher one step, either substracts or adds 2 to the value of the pairs, without changing the number of pairs. This is the same as shrinking on one side and growing on the other.
Now the question is, can we generate every even number S = P * M (except the powers of two), using these four operations within these boundaries?
Odd numbers S are trivial, because every odd number can be expressed as the sum of its halves +/- 0.5, which of course are consecutive integers.
I would like to present a proof based on a simple recursive algorithm as follows:
Step 0:
Let d be the depth of recursion starting at one d = 1.
Let S be an integer for which we want to check if it can be expressed as a sum of two or more consecutive positive integers.
Let the result set R be an ordered list that starts as empty.
Step 1: If S = 1 then exit concluding S cannot be a sum of consecutive positive integers.
Step 2: If S is even then halve it S := S/2; Increment depth d := d + 2; and go back to step 1.
Step 3: Insert (S – d)/2 at the head the result set R.
Append (S + d)/2 at the end of the result set R.
Decrement depth d := d – 2.
If d > 0, repeat from step 3.
Step 4: The result set R now contains the list of consecutive integers we wanted.
The above algorithm can be run for every positive integer and only powers of two will exit at step 1.
What the algorithm does is basically extracting factors of two out of the number, then halving the remaining odd factor, which gives a midpoint for the series, and then building as many pairs of lowest and highest integers around that midpoint as needed.
I believe your algorithm is flawed.
For instance, begin at S = 60: d = 1; R = {}1: Continue (S = 6)2: S = 3; d = 33: R = {0, 3}; d = 13: R = {1, 0, 3, 2}end
Also, it only finds one solution, and to me implies that only one exists. There are many numbers for which there are multiple solutions (15 = 4 + 5 + 6 = 7 + 8).
Oh, you’re right. The depth was supposed to fan out exponentially, but now it only grows linearly… It’s a bug. The version in my head should still work, but yes, this version is flawed. Thanks for testing it! Let me go back fixing…
The fix is to at Step 2 increment d := (2 * d) + 1, instead of always adding 2. Decrement at step 3 remains the same. The “insert” should also happen in the middle of the result set, and the “append” to the tail-side of middle, for correct ordering. Then the solution otherwise works, but still does not observe the boundary conditions, so it could propose also zero or negative numbers.