Hardy-RamanujanNumber

__author__ = 'VHarisop'
''' original idea from mpetyx <github.com/mpetyx> 
    Generates Hardy-Ramanujan Numbers up to 250000 in under 1 sec. 
'''
import sys
rng = int(sys.argv[1])

hrs = [0] * (2 * rng ** 3 + 1)

for x in range(1, rng):
    for y in range(x, rng):
        hrs[x**3 + y**3] += 1


for i in range(0, 2 * rng**3 + 1):
    if hrs[i] > 1:
        print i

While it is a clean and correct solution, it suffers from the fact that a large array needs to be allocated. Even though Python names them lists, their actual implementation is that of a C array (as opposed to, say, a linked list).

I toyed with the idea of using a dictionary instead, which would go something like this:

hrs = {}
for x in range(1, rng):
    for y in range(x+1, rng):
        val = x**3 + y**3
        if val in hrs:
            hrs[val].append((x,y))
        else:
            hrs[val] = [(x,y)]

However, this means that the complexity becomes O(n^3) since the in operator performs in O(n). Sorting a dictionary would also add a significant delay. Using collections.OrderedDict is even worse, as it takes almost double the time.

Presumably, using a sparse array implementation with some sort of B-tree indexing instead of a hash could reduce the "search for existence" portion to O(logn), but unless implementing it as a C-Python extension the performance would not be any different in practice.

In any case, unless there is a mathematical property for x, y, z, g in x^3 + y^3 = z^3 + g^3 that I am not aware of, algorithms of O(n^2) like your solution are the fastest way to go about this.

P.S. The [] * N syntax is indeed the fastest way to allocate an array, btw.

Initially (as can be seen in the revision history), I was using a class with the sum as key, and a set to contain the possible number tuples that generate it, with the intention of putting those in a, indeed sparse, array. But I was exploring what then became this version so I never tried out your way, which is pretty cool.

I am pretty familiar with B/B+ trees (and SWIG as well!), so if I find some spare time I might look into this solution. I don't think there is a mathematical property that holds for these numbers, but - concerning your method - there might be a way to generate them (at least) in a partially sorted order to make the most out of Python's Timsort.