Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# taxicab T(4)

By: ploffie on Nov 12th, 2012  |  syntax: Python  |  size: 1.06 KB  |  views: 50  |  expires: Never
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
clone this paste RAW Paste Data
Top