• Sign Up
• Login
• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# taxicab T(4)

ploffie Nov 12th, 2012 54 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
Top