-
-
Save VHarisop/09c2321c7d7ed8339540 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
__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 | |
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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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:
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
inx^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.