Speeding up a script -- looking for ideas

[William Park]

Richard Bow <donkan7 at yahoo.com> wrote:
> I'm hoping to get some hints for significantly speeding up the below 
> script. I've found 43 integers between 1 and 1,000,000 that satisfy the 
> condition, and would like to push on toward 10,000,000 in hopes of finding 
> an integer for which there are 3 pairs. Of course, another reason for 
> asking is to learn more Python from you guys.
> 
> Thanks in advance,
> 
> Richard Bow
> 
> ======================================================================
> # This finds integers n for which there are 2 pairs of positive integers,
> #(a,b) and (c,d) such that (a**3) + (b**3) = n, and (c**3) + (d**3) = n.
> # see http://www.mathpages.com/home/kmath028.htm 
> 
> start = 1000000
> end   = 2000000
> 
> import time
> t1= time.time()
> 
> for n in range(start, end + 1):
>    crn = int(n**(1/3.0)) + 2 #  because of float probs, add 2 to be sure 
>    list = []                 #  crn is large enough 
> 
>    for a in range(1,crn):
>        a3 = a ** 3 
>        for b in range(a,crn): 
>            b3 = b ** 3 
>            if a3 + b3 == n:                        
>                list = list + [(n,a,b)]
>                if len(list) >= 2:
>                # e.g. [(1729, 1, 12), (1729, 9, 10)] and 
>                        # [(994688, 29, 99), (994688, 60, 92)]
> 
>                    print list
>                    print
>                    
> t2 = time.time()
> print "Time's up!", t2 - t1, "seconds have elapsed"
> 
> print "EEEEEEEEEnnnnnnnnnnddddddddd"
> 
> ##total for n = 1 thru n = 1,000,000 is 43 integers
> ==========================================================


Well, brute-force method is not that bad.
Since you are calculating the pairs
    a^3 + b^3 = n, for n=[1,2000000]
where
    a=1, b=1,2,3,...,126
    a=2, b=2,3,4,...,126
    a=3, b=3,4,5,...,126
    ...
anyways, write a Python script to print them out.  Then, 'sort' and 'uniq'.

For example, consider script 'abn.py',
    maxn=2e6
    maxi=math.ceil(maxn**(1/3.0))
    for a in range(1, maxi+1):
	for b in range(a, maxi+1):
	    n = a**3 + b**3 
	    if n > maxn: break
	    print a, b, n
then,
    python abn.py | sort -n -k 3 | uniq -dc -f 2 > abn
spits out 64 integers in 0.23 second on my dual-P3/800.  And, going to 
    maxn=10e6
gives 150 integers in 0.65 second, and
    maxn=1e9
gives 1554 integers in 14.7 seconds.

You can search for 3 pairs just as easily.  There 8 integers with 3 pairs
for n < 1e9.

-- 
William Park, Open Geometry Consulting, <opengeometry at yahoo.ca>
Linux solution for data management and processing. 
1986 VW Jetta, 350000km :-))