Sums of consecutive whole numbers

[Swammerdami]

(No posts in this subforum for three months.)

Here's a nifty puzzle in arithmetic I just stumbled upon. It's too easy to excite serious mathematicians, but hard enough to challenge talented amateurs. Perfect!

Consider numbers that are equal to the sum of two or more consecutive positive integers. For examples 3=1+2; 9=2+3+4; 26=5+6+7+8.

Two puzzles:
(1) Determine the set of positive integers which CAN be expressed as the sum of two or more consecutive positive integers.
(Or equivalently, Determine the set of positive integers which CANNOT be expressed as the sum of two or more consecutive positive integers.)

(2) Prove your result.

(Nitpicking detail: replace "positive" with "non-negative" and one more case emerges: 1=0+1. Treat this special case whichever way you prefer.)

 

[Bomb#20]

Solution to Puzzle 1:

Show

The set of positive integers that are not powers of 2.

 

[Swammerdami]

Bravo Bomb#20 !!

As for Puzzle 2:
There *might* be a nifty proof based on base-2 arithmetic (Bomb#20's solutions have a special form) but I don't know how to do that.

I think I have a simple proof that starts with the observation that the b'th triangular number is

b×(b+1)÷2​

 

[Bomb#20]

Here's half a proof:

Show

The average of a sequence of an odd number of consecutive natural numbers is just the middle number, so the sum is just that middle number times the number of numbers, which is odd. So the sum is divisible by an odd number higher than 1.

A sequence of an even number of consecutive natural numbers doesn't have a middle number; it has a middle pair which is two adjacent numbers x and x+1 that add up to 2x+1, an odd number higher than 1. The middle pair is surrounded by another pair x-1 and x+2 that add up to the same odd number 2x+1. That pair is surrounded by another pair adding up to 2x+1, and so on through the whole sequence. The whole sequence adds up to some multiple of 2x+1. So once again the sum is divisible by an odd number higher than 1.

Powers of 2 are not divisible by odd numbers higher than 1. Therefore a sequence of natural numbers cannot add up to a power of 2.

 

[Swammerdami]

Bravo again, Mr. Bomb!

We seek to prove that

A whole number is NOT the sum of two or more consecutive whole numbers

IF AND ONLY IF​

that whole number is a power of two.​

You have proven the IF part. Left to prove is the ONLY IF.

 

[Don2 (Don1 Revised)]

Second half of proof:

Spoiler

What we have left are whole numbers with at least one odd factor. This we must prove can be represented as the sum of a consecutive sequence of whole numbers. It does not matter if they can be represented by more than one such sequence, we only need to show one and show it works for any generic whole number > 1 (all whole numbers > 1).

Let n = such whole number > 1 such that it is divisible by some odd factor k
Let p = n/k, then also p is a whole number

p = n / k ==> n = p * k

This is close to B20's first paragraph:
We take a sequence of k integers about p so that their center is p. We will have some number to the right of p, and some number to the left of p: ..., p-3, p-2, p-11, p, p+1, p+2, p+3, ... k is odd, so we could rewrite this as p-x, .... p, ... p+x where k = 2x+1. Not necessary.

So we have k numbers in the sequence and p is their center and average. Their sum is the whole number.

Now some of the numbers in the sequence can be negative integers. But since their sum is positive, their center is positive. This means that for any negative integer, there exists a positive integer in the sequence with the same magnitude. They, thus "cancel" each other. Likewise, a 0 in the sequence can be canceled since it is superfluous.

So we are left with a sequence of consecutive positive numbers whose sum is the natural number with an odd factor.

Examples:
25 = 5*5; n = 25; p = 5; k = 5; x = 2
3 + 4 + 5 + 6 + 7

10 = 2 * 5; n = 10; p = 2, k = 5, x = 2
0 + 1 + 2 + 3 + 4 = 10 which we can rewrite as 1 + 2 + 3 + 4

7 = 1 * 7; n = 7; p = 1; k = 7; x = 3
-2 + -1 + 0 + 1 + 2 + 3 + 4 = 7 which we can rewrite as 3 + 4

 

[Swammerdami]

And Kudos to Don2 too!

The solutions by Bomb#20 and Don2 (Don1 Revised) -- (may I call you Don2?) are much more straightforward than mine.

My approach is guaranteed to point to ALL ways to express the desired sum.
These appear to be the very same solution set that Don2 shows.

I'll just give the briefest outline:

Spoiler

The number of terms is either even (k=2x) or odd (k=2x+1).
In the even case, all numbers (x)(2x+2b+1) [with b≥0, x≥1] can be represented.
In the odd case, all numbers (2x+1)(x+b+1) [with b≥0, x≥1] can be represented.

For example, using 42 as the starting whole number, Don2's solution starts with its only odd factors 3, 7, 21
14 = 42/3 ===> 13+14+15
6 = 42/7 ===> 3+4+5+6+7+8+9
2 = 42/21 ===> -8+-7+-6+... +6+7+8 +9+10+11+12 = 9+10+11+12
These correspond to my (k,b) = (3,12) ; (7,2) ; (4,8)

I THINK -- maybe -- that the only solutions are the 1 solution per odd factor that Don2 derives.
Probably one of you will beat me to a proof of that fact.

Pedantic nitpickety Nitpick:
Somewhere near Don2's

"They, thus "cancel" each other. Likewise, a 0 in the sequence can be canceled since it is superfluous."​

I'd insert something like

"Obviously after the canceling we are left with at least TWO positive integers as required."​

 

[lpetrich]

I'll take a stab at this puzzle.

Show

Positive integers 1 and 2 cannot be expressed in this fashion, so we must consider all the rest.

The sum of all integers from n1 to n2 is (1/2) * (n1+n2) * (n2-n1+1)

Let n2 = n1+1. Then the sum is 2*n1+1. That means that every odd integer greater than one is the sum of two such integers.

So that leaves us with the even ones.

For n to n+2k, the sum is k*(n+2k-1)

For n to n+2k+1, the sum is (2k+1)*(2n+k-1)

That means for odd prime p, sums are always possible for multiples of p with a multiplying factor at least (p+1)/2.

It's hard for me to proceed further.

I have tried a numerical experiment, and I found that only powers of 2 cannot be expressed as such sums. But that result is only valid over the extent of my calculations.

 

[lpetrich]

Don's proof is a more general version of what I'd obtained. Here is what I think is a complete solution.

Show

The sum of m-k to m+k is (2k+1)*m

For this sum to be a sum over positive integers, m > k. But if it is not, then one can omit 0, and we can have all the negative numbers cancel out all the positive ones. That gives us a sum over k-m+1 to m+k, and that is in turn (2k+1)*m.

This means that every number with an odd factor can be expressed as the sum of consecutive positive integers, and those integers can be found from the original number and that factor.

That leaves numbers without odd factors: powers of 2.

To handle that case, we do a proof by contradiction, showing that every such sum has at least one odd factor.

The sum of m to m+2k is (m+k) * (2k+1)
The sum of m to m+2k+1 is (k+1) * (2m+2k+1)

Both possibilities have at least one odd factor.

Thus, powers of 2 cannot be expressed as the sum of consecutive positive integers, and only powers of 2.

 

[Swammerdami]

In how many distinct ways can a whole number be expressed as the sum of two or more consecutive whole numbers?

Spoiler: Partial

The following formulae are readily derived by noting that the sum of consecutive numbers is simply the difference of two triangular numbers.
The constraint x≥1 enforces that there be at least two numbers in that sum.

The number of terms is either even (k=2x) or odd (k=2x+1).​

In the even case, all numbers (x)(2x+2b+1) [with b≥0, x≥1] can be represented.​

In the odd case, all numbers (2x+1)(x+b+1) [with b≥0, x≥1] can be represented.​

For example, using 42 as the starting whole number, Don2's solution starts with its only odd factors [other than 1] 3, 7, 21
14 = 42/3 ===> 13+14+15
6 = 42/7 ===> 3+4+5+6+7+8+9
2 = 42/21 ===> -8+-7+-6+... +6+7+8 +9+10+11+12 = 9+10+11+12
These correspond to my (k,b) = (3,12) ; (7,2) ; (4,8)

I worked another example: 180 = 4*3*3*5. Now there are five odd factors other than 1 (3,5,9,15,45) and again there are five solutions:

k=2⋅4+0 ; b=18 =====> 19+20+...+26​

k=2⋅1+1 ; b=58 =====> 59+60+61​

k=2⋅2+1 ; b=33 =====> 34+35+...+38​

k=2⋅4+1 ; b=15 =====> 16+17+...+24​

k=2⋅7+1 ; b=4 ======> 5+6+...+19​

BUT there are three ways these constructions can fail.

Failure type 1 Example: 1440=32*3*3*5 (Too many 2's to cope with the largest odd factor)
The product of all the odd factors may be too small relative to twice the power-of-two residue. Extrapolating from the first line in the 180 example. we see that eventually the five predicted solutions shrink to 4:

45 :: k=2⋅1+0 ; b=21 = (45/1 - 2 - 1)/2 =====> 22+23​

90 :: k=2⋅2+0 ; b=20 = (90/2- 4 - 1)/2 =====> 21+22+23+24​

180 :: k=2⋅4+0 ; b=18 = (180/4 - 8 - 1)/2 =====> 19+20+...+26​

360 :: k=2⋅8+0 ; b=14 = (360/8 - 16 - 1)/2 =====> 15+16+...+30​

720 :: k=2⋅16+0 ; b=6 = (720/16 - 32 - 1)/2 =====> 7+8+...+38​

1440 :: k=2⋅32+0 ; b=-10 = (1440/32 - 64 - 1)/2 =====> FAILURE: b negative​

​

But note that, via the cancellations -9-8-...0+1+2+...+9 = 0 the (failing) sum of an even number of consecutive terms can be rewritten to be a redundant derivation of the longest odd-length sum!

1440 :: k=2⋅22+1 ; b=9 = (1440/45 - 22 - 1) =====> 10+11+...+54​

But we can't count that solution twice!

Failure types 2&3 Example: 138=2*3*23

k=2⋅2+0 ; b=32 = (138/2 - 4 - 1)/2 =====> 33+34+35+36​

k=2⋅6+0 ; b=5 = (138/6 - 12 - 1)/2 =====> 6+7+...+17​

k=2⋅1+1 ; b=44 = (138/3 - 1 - 1) =====> 45+46+47​

k=2⋅11+1 ; b=-6 = (138/23 - 11 - 1) FAILURE​

With three odd factors other than 1 (3, 23, 69), three solutions are predicted, but the 23 is too big and leads to failure.
BUT that is compensated by an extra even sum solution because 23 is large.

Do we always 'rob Peter to pay Paul"? Not so simple I'm afraid.. Given the goal as N=m*t where t is odd.the extra success MAY rely on t-2m > 0 and the extra failure may arise when t-m > 1.

I write "MAY" because I spent hours getting this far and it's time for another course of my daily physical therapy.
The (inconclusive) summary of N=m*t is incoherent, hurried, and probably wrong.

 

[Don2 (Don1 Revised)]

In how many distinct ways can a whole number be expressed as the sum of two or more consecutive whole numbers?

Here is my terrible answer:

Spoiler

I haven't given an explicit formula at present which is why I am saying that. The answer is the number of odd factors of n other than 1.

Because I am lazy, I wrote a quick script to merely show these work, i.e. do this for me and I have some examples using the numbers from Swammerdami's post. This isn't meant to be a proof.

42:
Odd factors: 3, 7, 21
-----------------------------------------
k=3 (p=14): 13 + 14 + 15 = 42
k=7 (p=6 ): 3 + 4 + 5 + 6 + 7 + 8 + 9 = 42
k=21 (p=2 ): 9 + 10 + 11 + 12 = 42

180:
Odd factors: 3, 5, 9, 15, 45
-----------------------------------------
k=3 (p=60): 59 + 60 + 61 = 180
k=5 (p=36): 34 + 35 + 36 + 37 + 38 = 180
k=9 (p=20): 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 = 180
k=15 (p=12): 5 + 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 = 180
k=45 (p=4 ): 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 = 180

1440:
Odd factors: 3, 5, 9, 15, 45
-----------------------------------------
k=3 (p=480): 479 + 480 + 481 = 1440
k=5 (p=288): 286 + 287 + 288 + 289 + 290 = 1440
k=9 (p=160): 156 + 157 + 158 + 159 + 160 + 161 + 162 + 163 + 164 = 1440
k=15 (p=96): 89 + 90 + 91 + 92 + 93 + 94 + 95 + 96 + 97 + 98 + 99 + 100 + 101 + 102 + 103 = 1440
k=45 (p=32): 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 + 18 + 19 + 20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + 29 + 30 + 31 + 32 + 33 + 34 + 35 + 36 + 37 + 38 + 39 + 40 + 41 + 42 + 43 + 44 + 45 + 46 + 47 + 48 + 49 + 50 + 51 + 52 + 53 + 54 = 1440

138:
Odd factors: 3, 23, 69
-----------------------------------------
k=3 (p=46): 45 + 46 + 47 = 138
k=23 (p=6 ): 6 + 7 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15 + 16 + 17 = 138
k=69 (p=2 ): 33 + 34 + 35 + 36 = 138

Let me now try to respond to some of Swammerdami's post, but my response will probably be too basic.

The number of terms is either even (k=2x) or odd (k=2x+1).

The number of terms pre-cancellation is always odd. After cancellation, it may be either odd or even. This is dependent upon the parity of n. The sum of two consecutive positive numbers is always odd and likewise for the sum of an even number of consecutive numbers. Meanwhile, the sum of an odd number of consecutive numbers is always even. So, post-cancellation, when we have only positive numbers, all even sums have only an odd number of terms and all odd sums have only an even number of terms.

Failure type 1 Example: 1440=32*3*3*5 (Too many 2's to cope with the largest odd factor)
The product of all the odd factors may be too small relative to twice the power-of-two residue. Extrapolating from the first line in the 180 example. we see that eventually the five predicted solutions shrink to 4:
45 :: k=2⋅1+0 ; b=21 = (45/1 - 2 - 1)/2 =====> 22+23
90 :: k=2⋅2+0 ; b=20 = (90/2- 4 - 1)/2 =====> 21+22+23+24
180 :: k=2⋅4+0 ; b=18 = (180/4 - 8 - 1)/2 =====> 19+20+...+26
360 :: k=2⋅8+0 ; b=14 = (360/8 - 16 - 1)/2 =====> 15+16+...+30
720 :: k=2⋅16+0 ; b=6 = (720/16 - 32 - 1)/2 =====> 7+8+...+38
1440 :: k=2⋅32+0 ; b=-10 = (1440/32 - 64 - 1)/2 =====> FAILURE: b negative

But note that, via the cancellations -9-8-...0+1+2+...+9 = 0 the (failing) sum of an even number of consecutive terms can be rewritten to be a redundant derivation of the longest odd-length sum!
1440 :: k=2⋅22+1 ; b=9 = (1440/45 - 22 - 1) =====> 10+11+...+54
But we can't count that solution twice!

This is interesting. It makes me wonder if extrapolating this at all is correct. Perhaps something else should be extrapolated. I simply don't know. Therefore, as an exercise, I will record the number of terms for each sequence for each sum. This way we can look for patterns.

Number of terms in each sequence. I have pre and post cancellation separated by -->.
45: 3, 5, 9, 15-->6, 45-->2
90: 3, 5, 9, 15-->12, 45-->4
180: 3, 5, 9, 15, 45-->8
360: 3, 5, 9, 15, 45-->16
720: 3, 5, 9, 15, 45-->32
1440: 3, 5, 9, 15, 45

My interpretation of the pattern (which we also see with 15) is that when the center is sufficiently low, the pre-cancellation sequence will contain negative numbers. If we keep multiplying by 2 (or some other prime), the center moves out of range so that the terms' bottom exceeds 0 and then the pre and post numbers are the same. Using variables from before k is the number of pre-cancellation terms. k is odd and can be expressed as 2x+1. p = n/k. So, if p-x <=0, there are negative terms. We can rewrite this many ways probably and some ways may be more insightful. p<= x for example or n/k <= (k-1)/2.

Or if we take the opposite, i.e. when pre = post, we could say n > k(k-1)/2. Let's check that for this case. n = 1440. k = 45; 1440 > 990. But for n=720, 720 < 990. **[990 is 45 x 44 / 2]

I apologize for using different meanings to same variable names that Swammerdami. This may make it confusing. Also, I know I haven't answered everything here.

 

[Don2 (Don1 Revised)]

Small error here:

Spoiler

The number of terms pre-cancellation is always odd. After cancellation, it may be either odd or even. This is dependent upon the parity of n. The sum of two consecutive positive numbers is always odd and likewise for the sum of an even number of consecutive numbers. Meanwhile, the sum of an odd number of consecutive numbers is always even. So, post-cancellation, when we have only positive numbers, all even sums have only an odd number of terms and all odd sums have only an even number of terms.