Given the natural number A, I want to find all pairs of natural numbers (B, C), so that B * C * (C + 1) = A

Question

What is the fastest way to do this?

My simple approach:

for (C = 1;C<sqrt(A);C++) { B=A/(C*(C+1)); if B is natural then add B,C to the list of possible pairs. } 

Is it possible to do this less than O (sqrt (A))?

Decision

As Egor Skriptunov says, this is easy to do in O (cube_root (A)).

Here is a simple javascript implementation.

 function findBCs(A) { if (A / 2 != Math.floor(A / 2)) return []; var solution = []; var i; var SR3 = Math.pow(A, 1 / 3); for (i = 1; i <= SR3; i++) { var B, C; C = i; B = A / (C * (C + 1)); if (B == Math.floor(B)) { solution.push([B, C]); } B = i; C = (-1 + Math.sqrt(1 + 4 * A / B)) / 2; if (C == Math.floor(C)) { solution.push([B, C]); } } return solution; } 

I accept Meh's answer because it should be better (also, the implementation is a bit more complicated and I haven't tested it).

Answer 1

Step 1: Factor A

Step 2: Find the set S of all divisors from prime factors A.

Step 3: For each divisor of c in S, check that c + 1 also divides A. If so, then b = A / (c * (c + 1)) is a solution. (This uses that c and c + 1 are coprime. Thus, if both c and c + 1 share A, then also c * (c + 1)).

The complexity of this depends on the method used for the AEg factor, if you implement, for example, Pollard-rho (which is relatively simple), then the complexity of the implementation is related to O (A ^ 0.25) in the worst case, and this is not the best answer . There is, of course, the best factoring algorithm. In addition, if your input is a special case with a large number of divisors, factoring can be easy, and the number of divisors is an extreme problem.

The advantage of this method is that you spend your time on a useful function (for example, factorization), which will simplify the solution of other similar problems. My own implementation of Pollard-rho in Python requires a total of 0.03 s for 20 examples with 15 digits sent to 6502, which at least speeds up the factor of 1000. More complex implementations should lead to significantly greater improvements.

For comparison, the quick and dirty Python implementation of the O (A ^ (1/3)) method proposed by Yegor Scriptunoff needs 0.7 s for the same list. This, of course, is a good result for a method that is easy to implement.

Answer 2

This can be done in O(cube_root(A))
Indeed, one of your numbers B and C must be less than cube_root(A)

Answer 3

This python works:

 from __future__ import division from math import sqrt def bcc1(a): ans = [] if a % 2: return ans # for odd a for b in range(1, a // 2 + 1): c = max(1, int(sqrt(a / b))) if b*c*(c+1) == a: ans.append((b,c)) return ans for a in range(2, 51, 2): print('a: %2i -> (b, c): %r' % (a, bcc1(a))) 

Output:

 a: 2 -> (b, c): [(1, 1)] a: 4 -> (b, c): [(2, 1)] a: 6 -> (b, c): [(1, 2), (3, 1)] a: 8 -> (b, c): [(4, 1)] a: 10 -> (b, c): [(5, 1)] a: 12 -> (b, c): [(1, 3), (2, 2), (6, 1)] a: 14 -> (b, c): [(7, 1)] a: 16 -> (b, c): [(8, 1)] a: 18 -> (b, c): [(3, 2), (9, 1)] a: 20 -> (b, c): [(1, 4), (10, 1)] a: 22 -> (b, c): [(11, 1)] a: 24 -> (b, c): [(2, 3), (4, 2), (12, 1)] a: 26 -> (b, c): [(13, 1)] a: 28 -> (b, c): [(14, 1)] a: 30 -> (b, c): [(1, 5), (5, 2), (15, 1)] a: 32 -> (b, c): [(16, 1)] a: 34 -> (b, c): [(17, 1)] a: 36 -> (b, c): [(3, 3), (6, 2), (18, 1)] a: 38 -> (b, c): [(19, 1)] a: 40 -> (b, c): [(2, 4), (20, 1)] a: 42 -> (b, c): [(1, 6), (7, 2), (21, 1)] a: 44 -> (b, c): [(22, 1)] a: 46 -> (b, c): [(23, 1)] a: 48 -> (b, c): [(4, 3), (8, 2), (24, 1)] a: 50 -> (b, c): [(25, 1)]