Hardy-RamanujanNumber

__author__ = 'dbatis'

def hardyRamanujan(upperLimit):
    """
    Computes all cases of x^3 + y^3 = z^3 + g^3, where x <> y <> z <> g and x, y, z, g < upperLimit.
 
    Example output:
    >>> hardyRamanujan(20)
    [[(1, 12, 1729), (9, 10, 1729)], [(2, 16, 4104), (9, 15, 4104)]]
 
    Each item in the list is a collection of (x, y, x^3 + y^3) tuples which all match the same
    sum.
    """
    # compute all possible sums where x != y, complexity O(n^2)
    sums = [(x, y, x**3 + y**3) for x in range(1, upperLimit) for y in range(x+1, upperLimit)]
 
    # sort it by resulting sum, complexity O(n * log(n))
    sums.sort(key=lambda x: x[2])
 
    results = []
 
    # iterate once on sorted list, complexity O(n)
    cmpVal = (0, 0, 0)
    resultValue = [cmpVal]
    for examinedVal in sums:
        if cmpVal[2] != examinedVal[2]:  # move on to next sum result
            cmpVal = examinedVal
            if len(resultValue) > 1:  # do we have previous matches to append to results?
                results.append(resultValue)
            resultValue = [cmpVal]
        else:
            resultValue.append(examinedVal)

    return results