javamathfactorization

Count number of integers in a given interval with two consecutive factors


I am trying to solve this problem which asks to find the number of integers in a given interval with consecutive factors x(x+1). 2 = 1 * 2, 6 = 2 * 3 etc.,

To find the count of numbers that can be decomposed into consecutive integers, This is the function I wrote that takes each positive integer in the range and multiply the integers on either side of its square root to determine if it can be decomposed into two consecutive integers.

I would like to know if there are any further optimizations that can be done with this solution.

public int solve(int a, int b) {
    int count = 0;
    for (int i = a; i <= b; i++) {
        if (i > 0 && i % 2 == 0) {
            int sqrt = (int) Math.floor(Math.sqrt(i));
            if (sqrt * (sqrt + 1) == i) {
                count++;
            }
        }
    }
    return count;
}

Solution

  • According to your solution, you need to count values that are doubled triangluar numbers.

    We can write expression for number of such values not exceeding some n

    x * (x+1) <=n
    x^2 + x - n <= 0
    

    Solving quadratic inequality and taking maximal x value:

    Discriminant = 1 + 4 * n
    x1, x2 = (-1 +- sqrt(Discriminant)) / 2
    we need positive root
    xmax = (-1 + sqrt(Discriminant)) / 2
    

    Now we count such values upto b (inclusively) and up to a (not counting a) and get difference.

    Example: F(100) = 9, F(11) = 2, so for range 12..100 we have 9-2=7 values (12,20,30,42,56,72,90)

    In Python (no language specific):

    from math import sqrt, floor
    def conseq(a, b):
        return floor((sqrt(1 + 4 * b) - 1) / 2) - floor((sqrt(4 * a - 3) - 1) / 2)
    

    Perhaps we might miss some values due to float math uncertainty (when flooring of d.999999999999999 gives d instead of d+1), so it is worth to make additional check:

    xb = floor((sqrt(1 + 4 * b) - 1) / 2)
    if (xb+1)*(xb+2)== b:
        xb += 1
    xa = floor((sqrt(4 * a - 3) - 1) / 2)
    if (xa+1)*(xa+2) == a - 1:
        xa += 1
    return xb - xa