Given a natural number A, I want to find all the pairs of natural numbers (B,C) so that B*C*(C+1) = A
algorithm, math
Solution
Step 1: Factor A
Step 2: Find the set S of all divisors from the prime factors of A.
Step 3: For each divisor c in S, check if c+1 divides A too. If it does 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 divide A then so does c*(c+1)).
The complexity of this depends on the method that is used for factor A. E.g., if you implement for example Pollard-rho (which is relatively simple) then the complexity of the implementation is about O(A^0.25) in the worst case. And this still isn't the best possible answer. There are of course better factoring algorithm. Also if your input is a special case with lots of divisors, then factoring can be easy and the number of divisors is the limiting problem.
The advantage of this method is of course that you'll spend your time on a generally useful function (i.e factorization), which will simplify solving other similar problems. My own implementation of Pollard-rho in Python needs a total of 0.03 s for the 20 examples with 15 digits posted by 6502, which is already at least a speedup of a factor 1000. More sophisticated implementations should lead to much larger improvements.
For comparison, a quick and dirty Python implementation of the O(A^(1/3)) method proposed by Egor Skriptunoff needs 0.7s for the same list. This is of course a good result for a method that is easy to implement.
Problem
What's the fastest way to do it? My simple aproach: ``` 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. } ``` Can it be done in less than O(sqrt(A))? Solution As Egor Skriptunoff answers, it can be done easily 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 (besides it's implementation is a little more complex and I have not tested).