7

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).

jbaylina
  • 4,408
  • 1
  • 30
  • 39
  • I don't think this works B never changes – aaronman Aug 17 '13 at 06:54
  • 1. It seems hard to believe that there are more pairs that meet this requirement. 2. You could only search those pairs through the `divisiors` of A, but this would still take O(sqrt(A)). – XCS Aug 17 '13 at 06:57
  • 5
    You could immediately bail out with empty set if A is odd number – mvp Aug 17 '13 at 06:57
  • @Cristy A=6 has solutions (1,2) and (3,1) – Henry Aug 17 '13 at 06:58
  • @Henry, yes you are right. But are there any other larger numbers to have multiple solutions? – XCS Aug 17 '13 at 07:01
  • 1
    @Cristy A=30: (1,5), (5,2), (15,1); I guess there are infinitely many examples – Henry Aug 17 '13 at 07:03
  • All even numbers have a C=1 solution for B=A/2, and for any A satisfying the equation, A, 2A, 3A, 4A, ... also satisfy for an adjustment in B. – Paul Aug 17 '13 at 07:18
  • 1
    I think you should try Mathematics stack exchange as well. – Paul Aug 17 '13 at 07:20
  • 5
    A=n! has a solution for C taking each value from 1 through n-1, so there is no finite upper bound on the number of solutions. – Patricia Shanahan Aug 17 '13 at 08:14
  • 1
    Do you need to perform this only for one number `A` or will they be multiple? – Boris Strandjev Aug 17 '13 at 08:55
  • @BorisStrandjev I realy need for many, but the question is just for one in order to simplify it. – jbaylina Aug 17 '13 at 10:27
  • 1
    @jbaylina This kind of simplification is a bit dangerous when asking algorithmic questions. There is such thing as amortized algorithm complexity - basically in series of queries you can afford long-lasting precalculation that will then decrease the complexity of each query. What is the limit for value of `A`? – Boris Strandjev Aug 17 '13 at 10:29
  • @BorisStrandjev I agree with your comment. In this problem, A is not limited and each A has no relation with each other. So that's why I simplified the question. Any way, if you have a good solution for a set of A's < M, I will apreciate the answer very much. – jbaylina Aug 17 '13 at 10:51

3 Answers3

4

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

Egor Skriptunoff
  • 23,359
  • 2
  • 34
  • 64
  • I don't understand this apparently trivial `O(cube_root(A))` solution... can you elaborate better by giving pseudocode for it? – 6502 Aug 17 '13 at 10:22
4

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.

meh
  • 56
  • 2
  • Nonsense, the number of divisors of a number is O(A^(c/loglog(A)), (for some small constant c) which is smaller than O(A^0.25). – meh Aug 17 '13 at 11:22
-1

This python seems to work:

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)))

The output produced is:

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)]
Paddy3118
  • 4,704
  • 27
  • 38