1 | initial version |
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...
2 | typo in the code |
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...
3 | better presentation |
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...