""" 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