7
\$\begingroup\$

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 nth 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")
\$\endgroup\$
  • \$\begingroup\$ This appears to give you the largest number less than roughly 3*500^3 which is the sum of 3 cubes in 12 different ways. Not the smallest such number. At the very least you should break out of the for loop once you've find i such that l[i] == l[i+12]. As @vnp mentions, you actually want i+11. \$\endgroup\$ – Amit Kumar Gupta Nov 12 '14 at 6:26
  • \$\begingroup\$ Also, how do you know that 501**3 + 1 + 1 isn't the smallest such number, but can only be expressed in 11 ways as the sum of three cubes less than or equal to 500? Why the artificial 500 bound? \$\endgroup\$ – Amit Kumar Gupta Nov 12 '14 at 6:50
5
\$\begingroup\$

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]))
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that my answer merely refactors the OP's code. I have not considered the mathematical validity of the method. \$\endgroup\$ – user27318 Nov 12 '14 at 7:12
  • 1
    \$\begingroup\$ combinations_with_replacement would also consider combinations where eg. i == j, like OP does. \$\endgroup\$ – Janne Karila Nov 12 '14 at 11:22
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.