How to get all the sets of consecutive numbers that add up to form a number?

Question

I wanna create a program that generates sets of consecutive numbers that add up to form a number. For example. if the input number is 15, it should give -

7, 8
4, 5, 6
1, 2, 3, 4, 5

Some formula/algorithm/loop that can do something that fits in. It could generate an array or print it. This may seem a math problem or silly question but I can't actually figure out how to do that programmatically in Java.

Please try to give exact code that can do the thing.

Answer 1

Say your input is N. You know each set of k consecutive numbers will be centered around N/k. A solution exists for even k if N/k ends with 0.5, and odd k if N/k is an integer. The solution, if one exists, is the k integers centered around N/k.

k=1: 15/1 = 15, so 15 (trivial; may want to omit)
k=2: 15/2 = 7.5, so 7,8
k=3: 15/3 = 5, so 4,5,6
k=4: 15/4 = 3.75, so no solution
k=5: 15/5 = 3, so 1,2,3,4,5
k=6: 15/6 = 2.5, so 0,1,2,3,4,5 
etc...
k=15: 15/15 = 1, so -6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8

You can easily modify this to limit to positive or nonnegative solutions.

Answer 2

I'll expand on @MBo's answer as it conveys a very clean algorithm. Wiki provides a good intro on arithmetic progressions, copied below for your convenience.

Sum

Derivation

The sum of a sequence starting with number a and consisting of n consecutive numbers:

S = (n/2) * [2 * a + (n-1) * d]

For consecutive numbers the step d is 1.

S = (n/2) * [2 * a + (n-1)]

Here we can transition to @MBo's post.

P = 2 * S = n * [2 * a + (n-1)]

We can iterate all possible counts of consecutive numbers n and check if the resulting a is valid (i.e. a is an integer).

Let's factor out a.

Say P = n * q => q = 2 * a + (n-1) => 2 * a = q - n + 1 => a = (q - n + 1) / 2

Filters

1) we mentioned we could iterate all possible counts of consecutive numbers n, but given p = n * q it's safe to say n needs to be a divisor of p.

• p % n == 0
• nMax = (int)Math.sqrt(p)

2) a is an integer and a = (q - n + 1) / 2 => (q - n + 1) is even => q - n is odd.

• ((q - n) & 1) == 1

Implementation

import java.util.*;
import java.lang.Math;
import java.util.stream.IntStream;
import static java.util.stream.Collectors.toList;

public class Progressions
{
    public static void main(String[] args)
    {
        List<List<Integer>> list = Calculate(15);
        System.out.print(list);
    }

    public static List<List<Integer>> Calculate(int s)
    {
        List<List<Integer>> list = new ArrayList<>();
        int p = 2*s;
        int nMax = (int)Math.sqrt(p);
        for (int n=2; n<=nMax; n++) {
            if(p % n == 0) {
                int q = p / n;
                if(((q - n) & 1) == 1) {          
                    int a = (q - n + 1) / 2;
                    list.add(range(a,n));
                }
            }
        }
        return list;
    }

    public static List<Integer> range(int a, int n) {
        return IntStream.range(a, a+n)
            .boxed()
            .collect(toList());
    }
}

Answer 3

Consecutive numbers form arithmetic progression. If it starts from number a and has n members, it's sum is

S = n * (2 * b + (n-1)) / 2
so
P = 2 * S = n * (2 * b + (n-1))

So for given input S we can factorize 2*S into all possible pairs of integer factors P = n * q where n<=q, then get starting number

a = (q - n + 1) / 2

If a is integer (oddity of q and n differs) then pair (a, n) represents valid sequence starting from a with n members

Example for S = 15, 2S = 30:

30 = 2 * 15 => n = 2, a = 7  => (7,8)
30 = 3 * 10 => n = 3, a = 4  => (4,5,6)
30 = 5 * 6 =>  n = 5, a = 1  => (1,2,3,4,5)

Simple Python example:

import math
def getseqs(s):
    print(s)
    p = 2 * s
    for n in range(2, math.ceil(math.sqrt(p))):
        if (p % n == 0):
            q = p // n
            if (((q - n) & 1) == 1):  #compare parity
                a = (q - n + 1) // 2
                seq = list(range(a, a+n))
                print(seq, sum(seq))

getseqs(17)
getseqs(15)
getseqs(72)

17
[8, 9] 17
15
[7, 8] 15
[4, 5, 6] 15
[1, 2, 3, 4, 5] 15
72
[23, 24, 25] 72
[4, 5, 6, 7, 8, 9, 10, 11, 12] 72

Answer 4

Consider the int input is your input number (ex. 15) and List<int[]> list as a storage of the result consecutive numbers, here you go:

List<int[]> list = new ArrayList<>();                          

int lower = 1;                               // Start searching from 1
int upper = (int) Math.floor(input + 1 / 2); // Up to the half of input (8+9 > 15)
while (lower < upper) {                      // Iterate between the bounds
    int sum = 0;
    for (int i = lower; i <= upper; i++) {   // Iterate and sum the numbers
        sum += i;
        if (sum == input) {                  // If it matches the input
                                             // Add the range to the List
                                             // You have to loop them by one and add to the
                                             // List before version Java-8
            list.add(IntStream
                         .range(lower, i + 1)
                         .toArray());
            break;                           // Found, no reason to continue 
        }
        if (sum > input) {                   // Terminate the loop if the sum overlaps
            break;
        }
    lower++;                                 // Increment and try the sums from 
                                             // a higher starting number
    sum = 0;                                 // Reset the sum
}

The result for the input 15 is a List of these arrays:

[1, 2, 3, 4, 5]
[4, 5, 6]
[7, 8]

Answer 5

Here's a suggestion:

For an input number N:

• you only have to consider numbers between 1 and N.
• you can maintain an interval that represents the current subset of [1,...,N]. Maintain the sum of the current interval. The first interval will be [1,1], and its sum is 1.
• As long as the sum < N, increase the right end of the interval by one (for example, you start with the interval [1,1]. Since 1 < N, you extend it to [1,2].
• If the sum of the current interval is equal to N, you add that interval to the output, remove the left end of the interval (also removing it from the current sum), and continue.
• If the sum exceeds N, you also remove the left end of the interval (also removing it from the current sum), and continue.
• You finish when the interval becomes [N,N] (which is the final interval you should add to the output).

For the input 15, here's how the interval will change over time:

Interval        Sum

[1]             1
[1,2]           3
[1,2,3]         6
[1,2,3,4]       10
[1,2,3,4,5]     15 -> output [1,2,3,4,5]
[2,3,4,5]       14
[2,3,4,5,6]     20
[3,4,5,6]       18
[4,5,6]         15 -> output [4,5,6]
[5,6]           11
[5,6,7]         18
[6,7]           13
[6,7,8]         21
[7,8]           15 -> output [7,8]
[8]             8
[8,9]           17
[9]             9
[9,10]          19
[10]
...
[15]            15 -> output 15

You can probably make some optimization once the sum of two consecutive numbers becomes higher than the target sum, at which point you can terminate the loop, and just add the final set (which contains just the target sum).