Writing cubic sums a better way

Question

I was asked the following problem:

What is the smallest positive integer n that can be written as a sum of three positive cubes in at least 12 ways?

Can this be coded better way such that it is easy to compute the smallest positive integer that is sum of m n^th powers? I'm not a professional programmer, so I managed only to write one solution that works.

l = list()
for i in range(1,500):
    for j in range(i,500):
        for k in range(j,500):
            l.append(i**3+j**3+k**3)
l.sort()
for i in range(0,len(l)-12):
    if l[i] == l[i+12]:
        number = l[i]
for i in range(1,500):
    for j in range(i,500):
        for k in range(j,500):
            if i**3+j**3+k**3 == number:
                print(str(number)+"="+str(i)+"^3+"+str(j)+"^3+"+str(k)+"^3")

Answer 1

Instead of three nested for loops, you can use itertools to enumerate combinations. Also, I would personally prefer to keep a count in a dictionary, as opposed to storing the same numbers over and over.

import itertools


cube_counts = {}

for i, j, k in itertools.combinations(range(1, 500), 3):
    cube = i**3 + j**3 + k**3
    cube_counts[cube] = cube_counts.get(cube, 0) + 1

print(min([cube for cube, count in cube_counts.items() if count >= 12]))

Answer 2

To begin with, the l[i] == l[i+12] condition implies that there are 13 ways to represent the number.

Second, since taxi-cab problem gave raise to some very deep mathematical insights, I seriously doubt that there is a nice way to attack a 3 cube problem - unless your name is Ramanujan.

Answer 3

Probably there's a more efficient mathematical solution. In any case, the algorithm can be improved, and there's also a bug.

---

First of all, I recommend to put 500 and 12 into variables, as you use them multiple times. You can define them near the top of the file where they will be easy to see and tweak if necessary. For example, since the run with 500 and 12 takes awfully long, I used smaller values like 50 and 4 for testing while refactoring.

min_count = 12
max_range = 500

---

You have two nested loops: first to calculate the cubes, and then again to find the numbers that add up to the smallest number you found. Assuming you have enough memory, you could use a single pass to calculate the cubes and at the same time store the i, j, k compoments, like this:

items = []
for i, j, k in itertools.combinations(range(1, max_range), 3):
    cube = i ** 3 + j ** 3 + k ** 3
    items.append((cube, (i, j, k)))

I renamed the original list from l (which is a very hard-to-read variable name) to items. Instead of the nested loops, I used @Luke's technique with itertools.combinations which is more compact.

In this version items is not a simple list of numbers, but a list of tuples: the cube + the tuple of (i, j, k). You can sort this list by the first element of the tuple (by the cube), by passing a comparison function to items.sort like this:

items.sort(lambda a, b: cmp(a[0], b[0]))

---

Finally, to print the items, it's more natural to use "".format instead of the complicated and hard to read string concatenation, like this:

for i in range(len(items) - min_count):
    if items[i][0] == items[i + min_count - 1][0]:
        number = items[i]
        for j in range(min_count):
            cube = items[i + j][0]
            x, y, z = items[i + j][1]
            print('{}={}^3+{}^3+{}^3'.format(cube, x, y, z))
        break