ploffie

taxicab T(4)

Nov 12th, 2012
85
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×