[Tutor] why?

[Paul McGuire]

Here is a solution for your problem that will compute the values up to
(5000,5000) in about 16 seconds:

upperlimit = 5000

cube = {}
for i in xrange(1,upperlimit):
    cube[i] = i*i*i

cubes = set(cube.itervalues())
for i in xrange(upperlimit, int(upperlimit*1.26)):
    cubes.add(i*i*i)

pairs = [(i,j) for i in range(1, upperlimit) 
                for j in range(i, upperlimit)
                if cube[i] + cube[j] + 1 in cubes]

for i,j in pairs:
    print i, j, 
    print int(round((cube[i] + cube[j] + 1) ** (0.33333333333))), 
    print cube[i] + cube[j] + 1


This program prints:
6 8 9 729
71 138 144 2985984
135 138 172 5088448
236 1207 1210 1771561000
242 720 729 387420489
372 426 505 128787625
426 486 577 192100033
566 823 904 738763264
575 2292 2304 12230590464
791 812 1010 1030301000
1938 2820 3097 29704593673
2676 3230 3753 52861038777

Since this smacks of homework, I'm guessing that your teacher will notice a
number of non-beginner Python techniques, and may suspect that you didn't
write this yourself.  Here are some suggestions on how to change this
program, or at least understand it better so you can pass it off as your
own:

1. Convert the list comprehension calculation of pairs back into a nested
for loop.
2. Explain why I used xrange instead of range.
3. Explain the purpose of the variables cube and cubes.
4. Explain why I computed the set of cubes up to upperlimit*1.26 (this was
not a number I just picked out of the air).
5. If this takes 16 seconds to run on my computer with an upperlimit of
5000, estimate how long this will it take to run up to your original
upperlimit of 10000000.

-- Paul