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

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) {
            int sqrt = (int) Math.floor(Math.sqrt(i));
            if (sqrt * (sqrt   1) == i) {
                count  ;
            }
        }
    }
    return count;
}

CodePudding user response：

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

CodePudding user response：

First of all your solution it does not seem to be correct and the condition i > 0 is the first reason I can spot on. Either the problem should read find the natural numbers or otherwise you should not exclude negatives integers. Take for example a = -6 and b = 9. Then -3 x -2 = 6 which does is in the -6 to 9 interval.

However considering you wanted naturals rather than integers then yes you can further optimise your code by iterating between a and (int) Math.floor(Math.sqrt(b)). No point in getting further as the result of multiplication will be greater than b

Hope this is enough for you to get you going. My answer is just a suggestion and I did not implemented and write unit tests to check it. On a real implementation you should do it.

For integers it will be a bit more complex.