Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

taxicab T(4)

By: ploffie on Nov 12th, 2012  |  syntax: Python  |  size: 1.06 KB  |  views: 45  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. """ segmented search for T(4)
  2.    --> 6963472309248 in 504 sec
  3. """
  4. from time import clock
  5. from collections import defaultdict
  6. import sys
  7.  
  8. def invpow(x, n):
  9.     """ x , n > 0 integers --> y ** n <= x and (y+1) ** n > x """
  10.     return int((x + 0.5) ** (1.0/3))
  11.  
  12. t0 = clock()
  13. N = 20000  
  14. ntriples = 4 # for original Ramanujan problem set to 2
  15. seg_size =  [300000000000, 600000000000] + [800000000000] * 100 # on 6 Gb mem
  16. cubs = [i ** 3 for i in xrange(N)]
  17. minseg = 1
  18. for segment in xrange(100):
  19.     results = defaultdict(int)
  20.     maxseg = minseg + seg_size[segment]
  21.     maxx = invpow(maxseg // 2, 3)
  22.     for x, x3 in enumerate(cubs[:maxx]):
  23.         miny = invpow(max(minseg - x3, 1),1)
  24.         miny = max(x, miny)
  25.         maxy = invpow(maxseg - x3, 3)
  26.         for y3 in cubs[miny:maxy]:
  27.             if minseg < x3 + y3 < maxseg:
  28.                 results[x3 + y3] += 1
  29.     sol = list(n for n in sorted(results.keys()) if results[n] == ntriples)
  30.     del results
  31.     if sol:
  32.         print sol
  33.         break
  34.     minseg = maxseg
  35.  
  36. # 6963472309248 in 504 sec