Count the number of ways an integer can be represented as a sum of consecutive positive integers

I am trying to count the number of ways an integer can be represented as sum of 2 or more consecutive positive integers. My Code is working in under 1 second for small inputs ($\le 10^7$) but after that it's taking too long. How can I lower the time complexity of the solution?

import java.io.*;

//sum needs to contain atleast 2 elements
public class IntegerRepresentedAsSumOfConsecutivePositiveIntegers
{
public static long count = 0;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long num = Long.parseLong(br.readLine()); //Enter a number( <=10^12)
//driver(num);
func(num);
System.out.println("count = " + count);
}

public static void func(long num)
{
long temp,i,j;
long limit = (num / 2);
for(i = 1 ; i <= limit ; i++)
{
temp = num;
j = i;
while(j < temp)
{
temp = temp - j;
j++;
}
if(j == temp)
{
count++;
}
}
}

}

• Hint based on @RE60K's answer: can you factor j*(j+1)/2 - i*(i+1)/2? What does this say about the number of possible solutions? Jun 16 '17 at 7:13

2 Answers

Some ideas that can improve the complexity:

• I am seeing that you are trying to equate num to i + (i+1) + ... + j, you can calculate this by j*(j+1)/2 - i*(i-1)/2

• Further for a given i if we assume that num = j*(j+1)/2 - i*(i+1)/2 we can solve the quadratic equation and check if we get integral roots, that makes the whole solution O(n)

• You may also wanna try looking up solutions to quadratic Diophantine equations, see here, after all j*(j+1)/2 - i*(i-1)/2 = num is a quadratic diophantine equation only.

What I would probably do

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ConsSum {

public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long num = Long.parseLong(br.readLine());
System.out.println("There are " + getConsSumWays(num) + " total way(s) to get " + num);
}

private static int getConsSumWays(long n) {
int count = 0;
/*
* i + (i+1) + (i+2) + ... + j = n
* => j(j+1)-i(i-1)=2n
* => let k = j(j+1) = 2n + i(i-1)
*/
for (long i = 0; i <= n / 2; i++) {
long k = 2 * n + i * (i - 1);
/*
* j^2+j-k=0 => j = [-1+sqrt(1+4k)]/2 since j>0
*/
long j = (long) ((-1 + Math.sqrt(1 + 4 * k)) / 2);
if (j * (j + 1) == k) {
System.out.println("sum [" + i + ".." + j + "] = " + n);
count++;
}
}
return count;
}

}

• actually i am not getting your what you are suggesting. it would be really great if you could ellaborate a bit more. thanks. :) Jun 10 '17 at 13:58

(Given a choice, I wouldn't read a single shortish input using file (or stream or channel) IO - just use an argument to main.)

static void func(long num) is neither documented nor named suggestively. It doesn't even live up to it's name, not returning a value, but using a class data member for result communication. This prevents multiple&concurrent use - instead, return a value.

RE60K (and jschnei) showed "analysis from the sum formula".
Alternatively, start from the sum target: to be a sum of two consecutive natural numbers, it needs to be odd. Tabulating this for several sum lengths:
# condition min 2 1 % 2 1 3 0 % 3 3 4 2 % 4 6 5 0 % 5 10 6 3 % 6 15 3, too 7 0 % 7 21 8 4 % 8 28 9 0 % 9 36 3, too 10 5 % 10 45 5, too 11 0 % 11 55 12 6 % 12 66 3, too 15 0 % 15 130 3, 5, too  using that, I get 1, 0, 2, 0, 1, 2, 1, 0, 2, 2, 1, 1, 1, 1, 4, 0, 1, 2, 1, 1, 4… ways to "consecutively sum to" n=1..21 (throwing this at OEIS yields - nothing. Going from 2 or more consecutive positive integers to 1: oeis.org/search?q=2,1,3,1,2,3,2,1,3,3,2,2,2,2,5,1,2,3,2,2,5 - in the FORMULA paragraph, you may find the generating function - and a description:)
number of odd divisors (including n), plus one if n is a triangular number (sum from 1..k for some k).

/** For a given <em>n</em>, compute the number of ways
*  to sum more than one consecutive natural number yielding <em>n</em>. */
// owes to an answer by RE60K@CR
class ConsSum {

public static void main(String[] args) throws NumberFormatException {
final long
from = args.length < 1 ? 42 : Long.parseLong(args[0]),
num = args.length < 2 ? from : Long.parseLong(args[1]);
System.out.println("There are");
for (long sum = from ; sum <= num ; sum++) {
final int ways = getConsSumWays(sum);
System.out.println(ways
+ Ending.forSingular(" way", ways) + " to get " + sum);
}
}

/** @return the number of ways to sum more than one consecutive
* natural number yielding <code>n</code>. */
private static int getConsSumWays(long n) {
int count = 0;
final long triangularCandidate = (long) (Math.sqrt(8*n + 1)/2);
final boolean triangular
= n == (triangularCandidate*(triangularCandidate+1))/2;
for (long divisor = 3 ; divisor <= n/2 ; divisor += 2)
if (0 == n % divisor)
count++;
return count + ((int)n & 1) + (triangular ? 1 : 0);
}
}
// for laughs:
/** stemming helpers etc */
class Ending {
static final java.util.regex.Pattern PLURALISER
= java.util.regex.Pattern.compile(".*(?:"
+ "(?<ies>[^aeiou]y)"
+ "|(?<es>ch|s|sh|x|z)"
+ "|[aeiou][aeiou]fe?|(?<ves>..fe?)"
+ ")");
static final String[] Plural = {
"ies",
};
/** Doesn't (yet) incorporate exceptions e.g. from
*  https://en.oxforddictionaries.com/spelling/plurals-of-nouns.
* @return given (a <code>String</code> ending in)
*  an English noun in singular, return the plural form. */
static String forSingular(final String singular, final int n) {
if (n == 1)
return singular;
final java.util.regex.Matcher pluraliser
= PLURALISER.matcher(singular);
if (pluraliser.matches()) {
int start;
if (0 <= (start = pluraliser.start("ies")))
return singular.substring(0, start+1) + "ies";
if (0 <= (start = pluraliser.start("es")))
return singular + "es";
if (0 <= (start = pluraliser.start("ves")))
return singular.substring(0, start+2) + "ves";
}
// regular
return singular + 's';
}
public static void main(String[] args) {
for (String s: new String[] {
"man", "child", "try", "way", "knife", "chief", "bus" })
System.out.println(s + " -> " + forSingular(s, 2));
}
}