Ask Your Question

Revision history [back]

Just to improve tmonteil answer you can use simple nested loops to enumerate solutions with the same "complexity" using the fact that your function d(a,b) is increasing in both variables:

def sol_iterator(n):
    a = floor(sqrt(2*n-1))
    b = 0
    while a != -1:
        while (a+1)*(b+1)*(a+b+2) < n:
            b += 1
        if (a+1)*(b+1)*(a+b+2) == n:
            yield a,b
        else:
            b -= 1
        a -= 1

and then list(sol_iterator(2*3065451)) runs in 8.33 ms which looks like a thousand times better !

And I am pretty sure that it is possible to do something more clever than increasing/decreasing by units in my function above...

Just to improve tmonteil answer you can use simple nested loops to enumerate solutions with the same "complexity" using the fact that your function d(a,b) is increasing in both variables:

def sol_iterator(n):
    a = floor(sqrt(2*n-1))
floor(sqrt(n-1))
    b = 0
    while a != -1:
        while (a+1)*(b+1)*(a+b+2) < n:
            b += 1
        if (a+1)*(b+1)*(a+b+2) == n:
            yield a,b
        else:
            b -= 1
        a -= 1

and then list(sol_iterator(2*3065451)) runs in 8.33 ms which looks like a thousand times better !

And I am pretty sure that it is possible to do something more clever than increasing/decreasing by units in my function above...

Just to improve tmonteil answer you can use simple nested loops to enumerate solutions with the same "complexity" using the fact that your function d(a,b) is increasing in both variables:

def sol_iterator(n):
    N = 2*n
a = floor(sqrt(n-1))
    floor(sqrt(N-1))
b = 0
 while a != -1:
     while (a+1)*(b+1)*(a+b+2) < n:
    N:
        b += 1
     if (a+1)*(b+1)*(a+b+2) == n:
N:
     yield print a,b
     else:
         b -= 1
     a -= 1

and then list(sol_iterator(2*3065451)) then, computing the solution for N=2*3065451 runs in 8.33 ms which looks like a thousand times better !

And I am pretty sure that it is possible to do something more clever than increasing/decreasing by units in my function above...