Sum and product in given range

Question

Given four positive integers , , and , is there a way to quickly find any two integers and such that:

• , and
• ?

When and , there is a closed-form solution to this using quadratic equations. We simply have to find the roots of and it will give us a suitable .

When , I know how to solve it in by noticing that the curve is convex and so we can just binary search for a suitable .

When , it can be solved in by factoring and looking for a pair of factors that sum to a value within the range.

When both of them are ranges, however, I can't think of any algorithm that can solve this efficiently. There are some possible heuristics, like fixing one of the two (iterating through the smaller range, etc.), or immediately reporting that no pair exists when the largest possible product that can be made with two integers summing to is smaller than , etc.

Unfortunately, I haven't been able to come up with anything that would work in the general case that is faster than iterating through everything in either or (possibly with some extra smaller factors). Is there a nice algorithm, or some fancy mathematics, that gives a faster solution?

Alternatively, is there a way to prove that iterating terminates quickly? (After handling some corner cases, etc.) I'm not interested in the number of valid pairs; finding any pair will do. It seems that iterating over the product and trying to find a corresponding sum tends to quickly find a solution if the range of allowable sums is sufficiently large. Could there be some sort of proof of this?

I would greatly appreciate any help!

Answer 1

You can solve it in O(sqrt(P2)) time.

1. Find these sums: small_sum = i + ceiling(P1/i) and big_sum = i + floor(P2/i) for i between 1 and sqrt(P2).

2. If small_sum > big_sum or big_sum < s1 or small_sum > s2 then i isn't partn of a solution. Move on.

3. Otherwise, max(small_sum, s1) min(big_sum, s2), and all values between "good sums." For any of these, let j = good_sum - i. Then i + j is a value between s1 and s2, and i * j is between p1 and p2.

We're checking at most sqrt(P2) values of i, and for each of these values we're doing constant work.

Edit -- Ruby implementation

def solve(s1, s2, p1, p2)
  max_i = (p2**0.5).floor
  1.upto(max_i) do |i|
    small_sum = i + (p1/i.to_f).ceil
    big_sum = i + (p2/i.to_f).floor
    next if big_sum < s1 || small_sum > s2 || big_sum < small_sum
    good_sum = [small_sum, s1].max
    puts "sum: #{i} + #{good_sum - i} = #{good_sum}, #{s1} <= #{good_sum} <= #{s2}"
    puts "product: #{i} * #{good_sum-i} = #{i*(good_sum-i)}, #{p1} <= #{i*(good_sum-i)} <= #{p2}"
    return
  end
  puts "no solution"
end