Hi,

Here's a sketch about how to do it. It's pretty late so it is not 100% complete, but it should still give the idea about how to solve it.

Well, for starters we can write the statement condition as: ab = k(a+b), with k>=1 and say b>a. Let S = a+b, M = b-a and P = a*b We have P = kS.

We also have: S^2 = a^2+b^2 + 2*P M^2 = a^2+b^2 — 2*P => P = [S^2-M^2]/4 => kS = [S^2-M^2]/4. => k = [S^2-M^2]/4S = (S+M)(S-M)/4S.

It is trivial that for any given S and M there exists exactly 1 unique solution for (a,b): b = (S+M)/2; a = (S-M)/2.

Now, for that solution to satisfy the problem statement, it must hold that: (S+M)(S-M)==0 (mod 4S) which means (1)^(2)^(3):

(1) (S+M)(S-M) mod 4 == 0 <=> S and M have the same parity (both odd or both even).

(2a) S is odd and (S+M)(S-M)/4 mod S == 0 => M * (S-M) == 0 mod S => MS — M^2 == 0 mod S => -M^2 == 0 mod S. => (S-1)*(-M^2) == 0 mod S => -S*M^2 + M^2 == 0 mod S => M^2 == 0 mod S, M is odd.

(2b) S is even => this is a more complicated case because you can no longer safely multiply by 4 above. Fortunately, a+b = 2k, a-b=2j <=> a/2+b/2 =k; a/2 — b/2 = j OR (a-1)/2+(b-1)/2=k, (a-1)/2-(b-1)/2=j, depending on the parity of (k+j)/2. So the case is reducible (eventually) to a case 2a. But the solutions a,b must have the same parity.

(3) (S+M)(S-M) >= 4S. => S^2 — M^2 — 4S >= 0 => M < = Sqrt(S^2-4S). Also, we must have (S+M)/2 < N.

So the answer to the problems is: R = How many pairs (M, S) are there such that the three conditions hold?

So here's how an algorithm might work: For all integers in the range 1..2N try that integer as a candidate S. Decompose it into prime factors (unless it was built from the prime factors up in which case you already have the decomposition): S = p1^k1*..*ps^ks. Now m^2 = j*S for some j>=1 iff the prime decomposition of m has, for prime pi exponent at least ceil(ki/2). How many M < candidate S are there which satisfy this condition? M = Q * p1^k1/2 * p2 ^k2/2 *..*ps^ks/2. So M = Q * M/Q. For a given S M/Q is fixed (and computable), so Q = 1..floor((S-1)/(M/Q)). Now out of those we must exclude those not of the same parity (if S is not divisible by 2, Q is neither) and also those who fall out of the range for the interval in condition (3) — just another upper limit on Q. Furthermore, special handling is required when S is even.

Here's the working for the second example: b<15 - 1 = 1 - 2 = 2 - 3 = 3 - 4 = 2^2 precomputed (1 solution) - 5 = 5 - 6 = 2*3 (reduces to S = 3, no solution) - 7 = 7 - 8 = 2^3 reduces to S=4, all solutions have same parity (1 solution) - 9 = 3^2 (M/Q = 3, Q = 1,3,5..8/3 = 1 [Q cannot be 2 because 9 is odd]) (1 solution) - 10 = 2*5 reduces to 5 - 11 = 11 - 12 = 2^2*3 (reduces to S=6, no solution) - 13 = 13 - 14 = 2*7 - 15 = 3*5 - 16 = 2^4 reduces to S=8, all solutions valid (1 solution) - 17 = 17 - 18 = 2*3^2 reduces to S=9, no solution with a,b same parity. - 19 = 19 - 20 = 2^2*5 (reduces to 2^5, no solution) - 21 = 3*7 - 22 = 2*11 (reduces to 11) - 23 = 23 - 24 = 2^3*3 (reduces to 12, no solutions) - 25 = 5^2 (M/Q = 5, Q=1,3,5..24/5; 2 Q but no solution in for b < 15) - 26 = 2*13 (reduces to 13, no solutions) - 27 = 3^3 = (M/Q = 9; Q = 1,3 .. 26/9; 1 Q but no solution for b < 15) - 28 = 2^2*7 (reduces to 14, no solution) -

It can be implemented to run in something like O(N) per test (just O(1) for counting the pairs for a particular S), but special care is needed for checking all boundary conditions.

Best, Mircea