Finding "taxiNumber" program, want to exchange nested for loop for optimization reasons

Question

I just started programming 1 week ago so please forgive the chaos you are about to see I'm trying to find the first x taxi numbers but with my "nested for loop" the program takes ages to go through all possibilities. Taxi number: if there is a number a^3+b^3 that is equal to c^3+d^3 that sum is a taxinumber. Example 12^3+1^3 == 10^3+9^3 == 1729

For me it's a success if i can find around 20 taxinumber Thanks beforehand for any tips or tricks!

Here is my code:

import math    

def main():    
    numbersOfResultsToFind = getNumberOfTaxisToFind()
    foundResults = 0
    numberToCheck = 1    
    while(foundResults < numbersOfResultsToFind):
        result = getTaxi(numberToCheck)
        if len(result) > 1: #if more then one a+b
            foundResults = foundResults + 1
            print(numberToCheck, result)
        numberToCheck = numberToCheck + 1

def getNumberOfTaxisToFind():
    return int(input("How many taxinumbers do you want to find? "))                           

def getThirdSquareFloored(value):
    value = value**(1/3)
    value = math.floor(value) #floor value
    return value    

def getTaxi(numberToCheck):
    result = []
    upperLimit = getThirdSquareFloored(numberToCheck)
    for a in range(1, upperLimit+1):
        for b in range(1, upperLimit+1):                                                          
            aCubed = a**3
            bCubed = b**3
            sumCub = aCubed + bCubed            
            if(sumCub == numberToCheck and a < b):
                result.append((a, b))
    return result   

main()

There are a few things you could change to speed things up. For exanple, the order of `a` and `b` does not matter, so you can reduce the checks if you remove the duplicates like 1, 2 and 2, 1 — meetaig, Sep 06 '16 at 18:42
Alright! Sounds good That would only speed up the program a bit though? I mean to find the first 15 or 20 taxis, is this something worth doing? — Niclas Löfvenmark, Sep 06 '16 at 18:50
if you need `a < b` then you should use `for b in range(a+1, ....)` — furas, Sep 06 '16 at 18:51
You should do `aCubed = a**3` before `for b in ...` - now you calculate many times the same value. — furas, Sep 06 '16 at 18:53
You can calculate `diffCubes = numberToCheck - aCubed` before `for b` and later compare `diffCub == bCubed` - this way you don't have to use `+` so many times. — furas, Sep 06 '16 at 18:58
Inside `for b` you can even do `if bCubed >= diffCub: break` to make less calculations. — furas, Sep 06 '16 at 19:00
The first taxinumber is 1729 a^3+b^3=c^3+d^3 or 12^3+1^3=10^3+9^3 but i was thinking if i set say a to: Instead of a^3+b^3=1729 a=(1729-b^3)^(1/3) I think I could in someway change my program to not use the "for b in range" with some slight adjustments. I'm just not sure how yet^^ — Niclas Löfvenmark, Sep 06 '16 at 19:06

score 0 · Answer 1 · edited May 23 '17 at 12:32

The problem is that the Taxicab numbers are VERY far apart. You can do some math tricks to solve it. For example, you can be checking the Euler's sum of powers. The problem with that approach is that you will be generating some taxi numbers, but they might not be in order.

As it goes to your code, I have some notes:

If you want to take the cubic root, do not do value**(1/3)! Remember that 1/3 = 0 in python. Use 1./3 or use numpy
Don't use the **(1./3) at all - any power functions are expensive, try replacing them with something (precomputed values?)
Important: Read StackOverflow if there is a solution already!

Thanks! Much appreciated I will try to not use power functions in the future! Not sure how to change it for this specific problem though! — Niclas Löfvenmark, Sep 07 '16 at 19:26

score 0 · Answer 2 · answered Sep 07 '16 at 19:24

import math           

def main():  
    numbersOfResultsToFind = getNumberOfTaxisToFind()
    foundResults = 0
    numberToCheck = 1 
    while(foundResults < numbersOfResultsToFind):
        result = getTaxi(numberToCheck)
        if len(result) > 1:
            foundResults = foundResults + 1
            print(numberToCheck, result)
        numberToCheck = numberToCheck + 1


def getNumberOfTaxisToFind():
    return int(input("How many taxinumbers do you want to find? "))


def getThirdSquareFloored(value):
    value = value**(1./3)
    value = math.floor(value)
    return value   

def getTaxi(numberToCheck):
    result = []
    upperLimit = getThirdSquareFloored(numberToCheck)
    for a in range(1, upperLimit+1):
        b = round((numberToCheck-a**3)**(1./3))
        if(a**3+b**3 == numberToCheck and a < b):
            result.append((a, b))
            if len(result) == 2:
                break
    return result
main()

Thanks so much for all help! This is my updated code, runs ALOT quicker. I set the b value to be calculated from a instead of using a nested for loop. I also implemented a if len(result), break in the end of my code No reason to keep looking for pairs if one is already found

Finding "taxiNumber" program, want to exchange nested for loop for optimization reasons

2 Answers2