Get the consecutive numbers whose sum matches with given number

Question

I was going through a simple program that takes a number and finds the number of occurrences of consecutive numbers that matches with given number.

For example:

if input is 15, then the consecutive numbers that sum upto 15 are:

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

So the answer is 3 as we have 3 possibilities here.

When I was looking for a solution I found out below answer:

static long process(long input) {
    long count = 0;
    for (long j = 2; j < input/ 2; j++) {
        long temp = (j * (j + 1)) / 2;
        if (temp > input) {
            break;
        }

        if ((input- temp) % j == 0) {
            count++;
        }
    }
    return count;
}

I am not able to understand how this solves the requirement because this program is using some formula which I am not able to understand properly, below are my doubts:

• The for loop starts from 2, what is the reason for this?
• long temp = (j * (j + 1)) / 2; What does this logic indicates? How is this helpful to solving the problem?
• if ((num - temp) % j == 0) Also what does this indicate?

Please help me in understanding this solution.

Answer 1

• If you put this tweak in it may fix code. I have not extensively tested it. It's an odd one but it puts the code through an extra iteration to fix the early miscalculations. Even 1/20000 would work! Had this been done with floats that got rounded down and 1 added to them I think that would have worked too:

  for (long j = 2; j < input+ (1/2); j++) {

In essence you need to only know one formula:

• The sum of the numbers m..n (or m to n) (and where n>m in code)
• This is ((n-m+1)*(n+m))/2

As I have commented already the code in the original question was bugged.

• See here.

  • Trying feeding it 3. That has 1 occurrence of the consecutive numbers 1,2. It yields 0.
  • Or 5. That has 2,3 - should yield 1 too - gives 0.
  • Or 6. This has 1,2,3 - should yield 1 too - gives 0.
  • In your original code, temp or (j * (j + 1)) / 2 represented the sum of the numbers 1 to j.

1 2 3 4 5
5 4 3 2 1
=======
6 6 6 6 6 => (5 x 6) /2 => 30/2 => 15

As I have shown in the code below - use System.out.println(); to spew out debugging info.

• If you want to perfect it make sure m and n's upper limits are half i, and i+1 respectively, rounding down if odd. e.g: (i=15 -> m=7 & n=8)

The code:

class Playground {
    private static class CountRes {
        String ranges;
        long count;
        CountRes(String ranges, long count) {
            this.ranges = ranges;
            this.count = count;
        }
        String getRanges() {
            return this.ranges;
        }
        long getCount() {
            return this.count;
        }
    }
    static long sumMtoN(long m, long n) {
        return ((n-m+1)* (n+m))/2;
    }
    static Playground.CountRes countConsecutiveSums(long i, boolean d) {
        long count = 0;
        StringBuilder res = new StringBuilder("[");
        for (long m = 1; m< 10; m++) {
            for (long n = m+1; n<=10; n++) {
                long r = Playground.sumMtoN(m,n);
                if (d) {
                        System.out.println(String.format("%d..%d %d",m,n, r));  
                } 
                if (i == r) {
                    count++;
                    StringBuilder s = new StringBuilder(String.format("[%d..%d], ",m,n));
                    res.append(s);
                }
            }
        }
        if (res.length() > 2) {
            res = new StringBuilder(res.substring(0,res.length()-2));
        }
        res.append("]");
        return new CountRes(res.toString(), count);
    }
    public static void main(String[ ] args) {
        Playground.CountRes o = countConsecutiveSums(3, true);
        for (long i=3; i<=15; i++) {
            o = Playground.countConsecutiveSums(i,false);
            System.out.println(String.format("i: %d Count: %d Instances: %s", i, o.getCount(), o.getRanges()));
        }
    }
}

You can try running it here

The output:

1..2 3
1..3 6
1..4 10
1..5 15
1..6 21
1..7 28
1..8 36
1..9 45
1..10 55
2..3 5
2..4 9
2..5 14
2..6 20
2..7 27
2..8 35
2..9 44
2..10 54
3..4 7
3..5 12
3..6 18
3..7 25
3..8 33
3..9 42
3..10 52
4..5 9
4..6 15
4..7 22
4..8 30
4..9 39
4..10 49
5..6 11
5..7 18
5..8 26
5..9 35
5..10 45
6..7 13
6..8 21
6..9 30
6..10 40
7..8 15
7..9 24
7..10 34
8..9 17
8..10 27
9..10 19
i: 3 Count: 1 Instances: [[1..2]]
i: 4 Count: 0 Instances: []
i: 5 Count: 1 Instances: [[2..3]]
i: 6 Count: 1 Instances: [[1..3]]
i: 7 Count: 1 Instances: [[3..4]]
i: 8 Count: 0 Instances: []
i: 9 Count: 2 Instances: [[2..4], [4..5]]
i: 10 Count: 1 Instances: [[1..4]]
i: 11 Count: 1 Instances: [[5..6]]
i: 12 Count: 1 Instances: [[3..5]]
i: 13 Count: 1 Instances: [[6..7]]
i: 14 Count: 1 Instances: [[2..5]]
i: 15 Count: 3 Instances: [[1..5], [4..6], [7..8]]

Answer 2

public static long process(long input) {
    long count = 0, rest_of_sum;
    for (long length = 2; length < input / 2; length++) {
        long partial_sum = (length * (length + 1)) / 2;
        if (partial_sum > input) {
            break;
        }
        rest_of_sum = input - partial_sum
        if (rest_of_sum % length == 0)
            count++;
    }
    return count;
}

input - given input number here it is 15

length - consecutive numbers length this is at-least 2 at max input/2

partial_sum = sum of numbers from 1 to length (which is a*(a+1)/2 for 1 to a numbers) assume this is a partial sequence

rest_of_sum = indicates the balance left in input

if rest of sum is multiple of length meaning is that we can add (rest_of_sum/length) to our partial sequence

lets call (rest_of_sum/length) as k

this only means we can build a sequence here that sums up to our input number starting with (k+1) , (k+2), ... (k+length)

this can validated now (k+1) + (k+2) + ... (k+length)

we can reduce this as k+k+k+.. length times + (1+2+3..length)

can be reduced as => k* length + partial_sum

can be reduced as => input (since we verified this now)

So idea here is to increment count every-time we find a length which satisfies this case here

Answer 3

NB: loop is starting from 2 because=> (1*(1+1))/2 == 1, which doesn't make sense, i.e, it doesn't effect on the progress;

let, k = 21;

1. so loop will iterate upto (k/2) => 10 times;

2. temp = (j*(j+1))/2 => which is, 3 when j =2, 6 when j = 3, and so on (it calculates sum of N natural numbers)

3. temp > k => will break the loop because, we don't need to iterate the loop when we got 'sum' which is more than 'K'

4. ((k-temp)%j) == 0 => it is basically true when the input subtracted from the sum of first j natural numbers are be divisible by j, if so then increment the count to get total numbers of such equation!

Answer 4

We need to find all as and ns, that for given b the following is true:

a + (a + 1) + (a + 2) + ... (a + (n - 1)) = b

The left side is an arithmetic progression and can be written as:

(a + (n - 1) / 2) * n = b         (*)

To find the limit value of n, we know, that a > 0, so:

(1 + (n - 1) / 2) * n = n(n + 1) / 2 <= b
n(n + 1) <= 2b
n^2 + n + 1/4 <= 2b + 1/4
(n + 1/2)^2 <= 2b + 1/4
n <= sqrt(2b + 1/4) - 1/2

Now we can rewrite (*) to get formula for a:

a = b / n - (n - 1) / 2

Example for b = 15 and n = 3:

15 / 3 - (3 - 1) / 2 = 4 => 4 + 5 + 6 = 15

And now the code:

double b = 15;
for (double n = 2; n <= Math.ceil(Math.sqrt(2 * b + .25) - .5); n++) {
    double candidate = b / n - (n - 1) / 2;
    if (candidate == (int) candidate) {
        System.out.println("" + candidate + IntStream.range(1, (int) n).mapToObj(i -> " + " + (candidate + i)).reduce((s1, s2) -> s1 + s2).get() + " = " + b);
    }
}

The result is:

7.0 + 8.0 = 15.0
4.0 + 5.0 + 6.0 = 15.0
1.0 + 2.0 + 3.0 + 4.0 + 5.0 = 15.0

Answer 5

I will try to explain this as simple as possible.

If input is 15, then the consecutive numbers that sum upto 15 are:

{1,2,3,4,5} -> 5 numbers
{4,5,6} -> 3 numbers
{7,8} -> 2 numbers

At worst case, this must be less than the Sum of 1st n natural numbers = (n*(n+1) /2.

So for a number 15, there can never be a combination of 6 consecutive numbers summing up to 15 as the sum of 1st 6 numbers =21 which is greater than 15.

Calculate temp: This is (j*(j+1))/2.

Take an example. Let input = 15. Let j =2.

temp = 2*3/2 = 3; #Meaning 1+2 =3

For a 2-number pair, let the 2 terms be 'a+1' and 'a+2'.(Because we know that the numbers are consecutive.)

Now, according to the question, the sum must add up to the number.

This means 2a+3 =15;

And if (15-3) is divisible by 2, 'a' can be found. a=6 -> a+1=7 and a+2=8

Similarly, let a+1 ,a+2 and a+3 a + 1 + a + 2 + a + 3 = 15 3a + 6 = 15 (15-6) must be divisible by 3.

Finally, for 5 consecutive numbers a+1,a+2,a+3,a+4,a+5 , we have 5a + 15 = 15; (15-15) must be divisible by 5.

So, the count will be changed for j =2,3 and 5 when the input is 15

If the loop were to start from 1, then we would be counting 1 number set too -> {15} which is not needed

To summarize:

1) The for loop starts from 2, what is the reason for this?

We are not worried about 1-number set here.

2) long temp = (j * (j + 1)) / 2; What does this logic indicates? How is this helpful to solving the problem?

This is because of the sum of 1st n natural numbers property as I have explained the above by taking a+1 and a+2 as 2 consecutive numbers.

3) if ((num - temp) % j == 0) Also what does this indicate?

This indicates the logic that the input subtracted from the sum of 1st j natural numbers must be divisible by j.

Answer 6

We are looking for consecutive numbers that sum up to the given number. It's quite obvious that there could be at most one series with a given length, so basically we are looking for those values witch could be the length of such a series. variable 'j' is the tested length. It starts from 2 because the series must be at least 2 long. variable 'temp' is the sum of a arithmetic progression from 1 to 'j'.

If there is a proper series then let X the first element. In this case 'input' = j*(X-1) + temp. (So if temp> input then we finished)

At the last line it checks if there is an integer solution of the equation. If there is, then increase the counter, because there is a series with j element which is a solution.

Actually the solution is wrong, because it won't find solution if input = 3. (It will terminate immediately.) the cycle should be:

for(long j=2;;j++)

The other condition terminates the cycle faster anyway.