## Consecutive Sums

### February 12, 2019

Given the positive integer 15, there are three ways to take consecutive positive integers that sum to 15: 1+2+3+4+5, 4+5+6 and 7+8.

Your task is to write a program that, given a positive integer, finds all the ways that consecutive positive integers can sum to the target integer. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 15 Responses to “Consecutive Sums”

1. Zack said

Quite a nifty one, reminiscent of Euler… Here is my take on it, using Julia 1.0:

function SumOfConsecutiveNumbers(x::Int64)
n = div(x,2)
n1 = n + 1
S = Array{Array{Int64}}(undef, n)
c = 0

``````for i = 1:n
for j = (i+1):n1
if sum(i:j) == x
c += 1
S[c] = collect(i:j)
break
end
end
end

return S[1:c]
``````

end

Cheers!

2. Ernie said

There is another way to solve the problem:

Let the series be k, k+1, k+2, …k+n = N

Then k(n+1) + n(n+1)/2 = N (1)
or (n+1)(n+2k) = 2N (2)

Thus we find all the divisors of 2N and solve for n and k. Some solutions do not give an integral value for k are therefore not valid.

3. matthew said

@Ernie: nice solution. Given 2N = ab, k is integral when a and b are of different parities, so we have a (non-trivial) series for N for each odd divisor of N (and this explains Praxis’s observation on 10^n,whose odd divisors are 5^i, 1 <= i <= n).

4. matthew said

Here’s some actual code for that solution:

Interval is [k..k+n] for n > 0, sum is k*(n+1)+ n(n+1)/2 = (n+1)(n+2k)/2
so 2N = ab with parity of a and b different. The odd one of a and b must
factor N, and any odd divisor of N will result in an interval sum:

```def cosums(N):
for a in range(1,N+1,2):
if N%a == 0:
# a is an odd divisor of N
b = 2*N//a
if b < a: a,b = b,a
n = a-1
k = (b-a+1)//2
yield(k,k+n)
```

An equivalent function to test cosums – the sum of integers between n and m (inclusive, with n <= m) is (m-n+1)(m+n)/2 decreasing n increases this product and decreasing m decreases the product:

```def cosums1(N):
n,m = N,N
while n > 0:
t = (m-n+1)*(m+n)//2
if t < N: n -= 1
elif t > N: m -= 1
else:
yield (n,m)
n -= 1; m -= 1
```

And for a test, print out the numbers where there are more solutions than any lower number:

```maxlen = 0
for N in range(200):
s = sorted(list(cosums(N)))
s1 = sorted(list(cosums1(N)))
assert(s == s1)
if len(s)> maxlen:
print(N,s)
maxlen = len(s)
```

Looks like we are generating https://oeis.org/A053624, Highly Composite Odd Numbers:

```1 [(1, 1)]
3 [(1, 2), (3, 3)]
9 [(2, 4), (4, 5), (9, 9)]
15 [(1, 5), (4, 6), (7, 8), (15, 15)]
45 [(1, 9), (5, 10), (7, 11), (14, 16), (22, 23), (45, 45)]
105 [(1, 14), (6, 15), (12, 18), (15, 20), (19, 23), (34, 36), (52, 53), (105, 105)]
```
5. Globules said

A quick and dirty Haskell version.

```import Data.Maybe (mapMaybe)
import System.Environment (getArgs)
import Text.Printf (printf)

sumTo :: Integral a => a -> a -> a
m `sumTo` n = (n + m) * (n - m + 1) `quot` 2

sumBounds :: Integral a => a -> [(a, a)]
sumBounds n = let u = n `quot` 2
in [(i, j) | i <- [1..u], j <- [i+1..u+1], i `sumTo` j == n]

consecSums :: Integral a => a -> [[a]]
consecSums = map (uncurry enumFromTo) . sumBounds

printConsecSums :: Int -> IO ()
printConsecSums n = print n >> mapM_ (printf "    %s\n" . show) (consecSums n)

main :: IO ()
main = do
ns <- mapMaybe readMaybe <\$> getArgs
mapM_ printConsecSums ns
```
```\$ ./consecsums 1 3 9 15 45 105
1
3
[1,2]
9
[2,3,4]
[4,5]
15
[1,2,3,4,5]
[4,5,6]
[7,8]
45
[1,2,3,4,5,6,7,8,9]
[5,6,7,8,9,10]
[7,8,9,10,11]
[14,15,16]
[22,23]
105
[1,2,3,4,5,6,7,8,9,10,11,12,13,14]
[6,7,8,9,10,11,12,13,14,15]
[12,13,14,15,16,17,18]
[15,16,17,18,19,20]
[19,20,21,22,23]
[34,35,36]
[52,53]
```
6. Smith said
```def solution(limit=15, verbose=False):
solutions, stack = list(), 
while True:
s, l = sum(stack), len(stack)

# print
if verbose: print('{} {}'.format('*' if s == limit else '', stack))

# check
if s == limit: solutions.append(stack.copy())
if s > limit and l <= 2: break

# update
if s < limit: stack.append(stack[-1] + 1)
elif s >= limit: stack.pop(0)

return solutions

solution(limit=15, verbose=True)
```
``` 
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
* [1, 2, 3, 4, 5]
[2, 3, 4, 5]
[2, 3, 4, 5, 6]
[3, 4, 5, 6]
* [4, 5, 6]
[5, 6]
[5, 6, 7]
[6, 7]
[6, 7, 8]
* [7, 8]

[8, 9]
```
7. Carl Vereen said

Hello Everyone,

This is my first post. I am very new to programming and wanted to improve with some problem solving. Here is my solution using Javascript. I definitely did not make the output pretty. Hope this post works. Thanks

```
const consecutivePositiveInt = (target) => {

let currentSum;
let history = [];
let startNum;
let answerArray = [];
for (let k =1; k < target; k++) {
startNum = k;
currentSum = k;
history.push(startNum);

while (currentSum < target) {
currentSum = history.reduce(( accumulator, currentValue ) => accumulator + currentValue, 0);
if(currentSum == target) {
history = [];
} else if (currentSum > target) {
history = [];
} else {
startNum++;
history.push(startNum);
}
}

}

if(answerArray === undefined || answerArray.length === 0){
return `No Consecutive Positive numbers add to the number \${target}`
}else{
}

}

```
8. Steve said

Can’t seem to post my entry

9. Jim said
```
Klong version 2

" Consecutive Sums"

"f(x;y) returns the divisor plus the first number in the series for a given number and divisor, as f(85;2)->[2 42].  If there is no series for a divisor, it returns [0 0] as f(85;3)->[0 0]"

f::{[r]; r::(x-(+/!y))%y; :[(r=((_r)%1.0))>0; y,_r; [0 0]]}

"g(x) returns all pairs of divisors and series start numbers for a given number, as g(85)->[[2 42] [5 15] [10 4]]"

g::{[l n]; l::[]; n::x; {t::f(n;x); ~0>(t@1)} {:[(0=t@0)|(0=t@1); t; l::l,(,t)]; x+1}:~2; l}

"h(x) changes the divisor/series start number pairs from g(x) to lists of the series themselves, as h(g(85))->[[42 43] [15 16 17 18 19] [4 5 6 7 8 9 10 11 12 13]]"

h::{[l l2]; l::x; l2::[]; {[m n]; m::x@0; n::x@1; n+!m}'l}

"go(x) displays the number, ' --> ' and the lists of series, as in '85 --> [[42 43] [15 16 17 1819] [4 5 6 7 8 9 10 11 12 13]]'"

go::{.d(x); .d(" --> "); .p(h(g(x)))}

"go'2+!100 applies go to the list of numbers from 2 to 101: It is interesting to note that none of the numbers which are powers of 2 have lists, but all of the others do"

go'2+!100

./kg -l consecutive_sums.kg
2 --> []
3 --> [[1 2]]
4 --> []
5 --> [[2 3]]
6 --> [[1 2 3]]
7 --> [[3 4]]
8 --> []
9 --> [[4 5] [2 3 4]]
10 --> [[1 2 3 4]]
11 --> [[5 6]]
12 --> [[3 4 5]]
13 --> [[6 7]]
14 --> [[2 3 4 5]]
15 --> [[7 8] [4 5 6] [1 2 3 4 5]]
16 --> []
17 --> [[8 9]]
18 --> [[5 6 7] [3 4 5 6]]
19 --> [[9 10]]
20 --> [[2 3 4 5 6]]
21 --> [[10 11] [6 7 8] [1 2 3 4 5 6]]
22 --> [[4 5 6 7]]
23 --> [[11 12]]
24 --> [[7 8 9]]
25 --> [[12 13] [3 4 5 6 7]]
26 --> [[5 6 7 8]]
27 --> [[13 14] [8 9 10] [2 3 4 5 6 7]]
28 --> [[1 2 3 4 5 6 7]]
29 --> [[14 15]]
30 --> [[9 10 11] [6 7 8 9] [4 5 6 7 8]]
31 --> [[15 16]]
32 --> []
33 --> [[16 17] [10 11 12] [3 4 5 6 7 8]]
34 --> [[7 8 9 10]]
35 --> [[17 18] [5 6 7 8 9] [2 3 4 5 6 7 8]]
36 --> [[11 12 13] [1 2 3 4 5 6 7 8]]
37 --> [[18 19]]
38 --> [[8 9 10 11]]
39 --> [[19 20] [12 13 14] [4 5 6 7 8 9]]
40 --> [[6 7 8 9 10]]
41 --> [[20 21]]
42 --> [[13 14 15] [9 10 11 12] [3 4 5 6 7 8 9]]
43 --> [[21 22]]
44 --> [[2 3 4 5 6 7 8 9]]
45 --> [[22 23] [14 15 16] [7 8 9 10 11] [5 6 7 8 9 10] [1 2 3 4 5 6 7 8 9]]
46 --> [[10 11 12 13]]
47 --> [[23 24]]
48 --> [[15 16 17]]
49 --> [[24 25] [4 5 6 7 8 9 10]]
50 --> [[11 12 13 14] [8 9 10 11 12]]
51 --> [[25 26] [16 17 18] [6 7 8 9 10 11]]
52 --> [[3 4 5 6 7 8 9 10]]
53 --> [[26 27]]
54 --> [[17 18 19] [12 13 14 15] [2 3 4 5 6 7 8 9 10]]
55 --> [[27 28] [9 10 11 12 13] [1 2 3 4 5 6 7 8 9 10]]
56 --> [[5 6 7 8 9 10 11]]
57 --> [[28 29] [18 19 20] [7 8 9 10 11 12]]
58 --> [[13 14 15 16]]
59 --> [[29 30]]
60 --> [[19 20 21] [10 11 12 13 14] [4 5 6 7 8 9 10 11]]
61 --> [[30 31]]
62 --> [[14 15 16 17]]
63 --> [[31 32] [20 21 22] [8 9 10 11 12 13] [6 7 8 9 10 11 12] [3 4 5 6 7 8 9 10 11]]
64 --> []
65 --> [[32 33] [11 12 13 14 15] [2 3 4 5 6 7 8 9 10 11]]
66 --> [[21 22 23] [15 16 17 18] [1 2 3 4 5 6 7 8 9 10 11]]
67 --> [[33 34]]
68 --> [[5 6 7 8 9 10 11 12]]
69 --> [[34 35] [22 23 24] [9 10 11 12 13 14]]
70 --> [[16 17 18 19] [12 13 14 15 16] [7 8 9 10 11 12 13]]
71 --> [[35 36]]
72 --> [[23 24 25] [4 5 6 7 8 9 10 11 12]]
73 --> [[36 37]]
74 --> [[17 18 19 20]]
75 --> [[37 38] [24 25 26] [13 14 15 16 17] [10 11 12 13 14 15] [3 4 5 6 7 8 9 10 11 12]]
76 --> [[6 7 8 9 10 11 12 13]]
77 --> [[38 39] [8 9 10 11 12 13 14] [2 3 4 5 6 7 8 9 10 11 12]]
78 --> [[25 26 27] [18 19 20 21] [1 2 3 4 5 6 7 8 9 10 11 12]]
79 --> [[39 40]]
80 --> [[14 15 16 17 18]]
81 --> [[40 41] [26 27 28] [11 12 13 14 15 16] [5 6 7 8 9 10 11 12 13]]
82 --> [[19 20 21 22]]
83 --> [[41 42]]
84 --> [[27 28 29] [9 10 11 12 13 14 15] [7 8 9 10 11 12 13 14]]
85 --> [[42 43] [15 16 17 18 19] [4 5 6 7 8 9 10 11 12 13]]
86 --> [[20 21 22 23]]
87 --> [[43 44] [28 29 30] [12 13 14 15 16 17]]
88 --> [[3 4 5 6 7 8 9 10 11 12 13]]
89 --> [[44 45]]
90 --> [[29 30 31] [21 22 23 24] [16 17 18 19 20] [6 7 8 9 10 11 12 13 14] [2 3 4 5 6 7 8 9 10 11 12 13]]
91 --> [[45 46] [10 11 12 13 14 15 16] [1 2 3 4 5 6 7 8 9 10 11 12 13]]
92 --> [[8 9 10 11 12 13 14 15]]
93 --> [[46 47] [30 31 32] [13 14 15 16 17 18]]
94 --> [[22 23 24 25]]
95 --> [[47 48] [17 18 19 20 21] [5 6 7 8 9 10 11 12 13 14]]
96 --> [[31 32 33]]
97 --> [[48 49]]
98 --> [[23 24 25 26] [11 12 13 14 15 16 17]]
99 --> [[49 50] [32 33 34] [14 15 16 17 18 19] [7 8 9 10 11 12 13 14 15] [4 5 6 7 8 9 10 11 12 13 14]]
100 --> [[18 19 20 21 22] [9 10 11 12 13 14 15 16]]
101 --> [[50 51]]
Klong 20190209
xxx
```

yyy

10. Richard A. O'Keefe said
```/* In fact there are FOUR ways to take consecutive integers summing
to 15:  is another solution.

Suppose the w numbers starting at p (p, ..., p-1+w) add up to n.
This is wp + w(w-1)/2.  So w(2p+w-1) = 2n.
We must have w divides 2n and 2p+w-1 = 2n/w, so
for w = 1, 2, ... while w*w < 2n
if w divides 2n then
t := 2n/w - w + 1
if t is even then
(t/2,w) is a solution
*/
#include <stdio.h>
#include <stdlib.h>

static void consecs(int n) {
int w, q, r, t;

printf("%d:\n", n);
n += n;
w = 0;
while (w++, w*w < n) {
if (n % w == 0) {
t = n / w - w + 1;
if ((t&1) == 0) printf("    %d@%d\n", w, t>>1);
}
}
printf("\n");
}

int main(int argc, char **argv) {
if (argc < 2) {
consecs(15);
} else
for (int i = 1; i < argc; i++) {
consecs(atoi(argv[i]));
}
return 0;
}```
11. Richard A. O'Keefe said

What in the name of sanity happened to my lovely indentation?

12. matthew said

ie. do something like this:

```[code lang="c"]
int main() {
return 0;
}
[/code]
```
13. programmingpraxis said

@richard: I think I got the formatting fixed properly. Let me know if I did something wrong. The easiest way to post code is just to wrap it with pre … /pre tags.

14. Daniel said

Here’s a solution in C.

```#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {
if (argc != 2) return EXIT_FAILURE;
int x = atoi(argv);
for (int i = 1;; ++i) {
int y = x / i;
int z = y - i / 2 + !(i % 2);
if (z < 1) break;
int sum = i * y;
if (i % 2 == 0) sum += i / 2;
if (sum == x) {
for (int j = z; j < i + z; ++j) {
if (j > z) printf("+");
printf("%d", j);
}
printf("\n");
}
}
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./a.out 3
3
1+2

\$ ./a.out 10
10
1+2+3+4

\$ ./a.out 15
15
7+8
4+5+6
1+2+3+4+5

\$ ./a.out 20
20
2+3+4+5+6

```