1
$\begingroup$

I am trying to understand the question -:

Given a number N, write a function to express N as sum of two or more consecutive positive numbers. If there is no solution, output -1. If there are multiple solution, then print one of them.

Examples:

Input : N = 10 Output : 4 + 3 + 2 + 1

Input : N = 8 Output : -1

Input : N = 24 Output : 9 + 8 + 7

Link

Here I got the explanation.

Sum of first n natural numbers = n * (n + 1)/2

Sum of first (n + k) numbers = (n + k) * (n + k + 1)/2

If N is sum of k consecutive numbers, then
following must be true.

N = [(n+k)(n+k+1) - n(n+1)] / 2

OR 

2 * N = [(n+k)(n+k+1) - n(n+1)]

But the problem arises in the code.

static void findConsecutive(int N)
{
    for (int last=1; last<N; last++)
    {
        for (int first=0; first<last; first++)
        {
            if (2*N == (last-first)*(last+first+1))
            {
                System.out.printf(N + " = ");
                printConsecutive(last, first+1);
                return;
            }
        }
    }
    System.out.print("-1");
}

I am not able to get why it is using

2*N == (last - first) * (last + first + 1);

Please help.

$\endgroup$
5
  • $\begingroup$ If $N$ has an odd prime factor $p$ it can be expressed as the same of $p$ consecutive integers. Otherwise it is a power of $2$. The integers in the first case need not be positive, though. $\endgroup$ Oct 15, 2017 at 6:35
  • $\begingroup$ @MarkBennet So what is the relationship between 2*N == (last - first) * (last + first + 1); and your comment? I have the idea of calculating the number of ways. $\endgroup$ Oct 15, 2017 at 6:43
  • 1
    $\begingroup$ Actually if $first$ is the first of the consecutive integers and $last$ the last, it should be $$\sum_{j=first}^{last} j = last(last+1)/2 - (first-1)(first)/2 = (last+first)(last+1-first)/2$$ $\endgroup$ Oct 15, 2017 at 6:49
  • $\begingroup$ I also thought so. So there it is given wrong. $\endgroup$ Oct 15, 2017 at 6:55
  • $\begingroup$ @RobertIsrael Please rewrite your comment as answer as this is the valid solution and explanation of my question. $\endgroup$ Jun 19, 2018 at 4:08

2 Answers 2

1
$\begingroup$

(As requested, turning the comment into an answer)

Actually if $first$ is the first of the consecutive integers and $last$ the last, it should be $$ \sum_{j=first}^{last} j = last(last+1)/2 - (first-1)(first)/2 = (last+first)(last+1-first)/2 $$

$\endgroup$
1
$\begingroup$

Note that: $$(n+k)(n+k+1) - n(n+1)=2nk+k^2+k=(2n+k+1)k=\\ ((\underbrace{n+k}_{last})+(\underbrace{n+1}_{first}))((\underbrace{n+k}_{last})-(\underbrace{n+1}_{first})+1).\\ $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .