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

Question

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++;
            }
        }
    }

}

Answer 1

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;
    }

}

Answer 2

(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));
    }
}