""" segmented search for T(4)
    --> 6963472309248 in 504 sec
"""
from time import clock
from collections import defaultdict
import sys

def invpow(x, n):
    """ x , n > 0 integers --> y ** n <= x and (y+1) ** n > x """
    return int((x + 0.5) ** (1.0/3))

t0 = clock()
N = 20000  
ntriples = 4 # for original Ramanujan problem set to 2
seg_size =  [300000000000, 600000000000] + [800000000000] * 100 # on 6 Gb mem
cubs = [i ** 3 for i in xrange(N)]
minseg = 1
for segment in xrange(100):
    results = defaultdict(int)
    maxseg = minseg + seg_size[segment]
    maxx = invpow(maxseg // 2, 3)
    for x, x3 in enumerate(cubs[:maxx]):
        miny = invpow(max(minseg - x3, 1),1)
        miny = max(x, miny)
        maxy = invpow(maxseg - x3, 3)
        for y3 in cubs[miny:maxy]:
            if minseg < x3 + y3 < maxseg:
                results[x3 + y3] += 1
    sol = list(n for n in sorted(results.keys()) if results[n] == ntriples)
    del results
    if sol:
        print sol
        break
    minseg = maxseg

# 6963472309248 in 504 sec