Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """ 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement