Finding all possible sums of three integers within a list

I need to use a list of perfect cubes to find all possible sums of three different numbers within that list. The sum must also be a perfect cube. My original solution was to nest 3 for loops to cover each number, but this tends to become quite inefficient, as the aforementioned list can be very long. For instance, the cubes list could contain all cubes lower than 6'000'000.

cubes = [1, 8, 27, 64, 125]

for item in cubes:
    for item2 in cubes: 
        for item3 in cubes:
            sum = item + item2 + item3
            if numpy.cbrt(sum) == int(numpy.cbrt(sum)):
                print(sum)

Does anyone have a more efficient way to do this?

Your code uses three nested for loops to iterate over each item in the cubes list three times, which can become inefficient for larger lists. One way to optimize the code is to use a combinations function from the itertools module to generate all possible combinations of three items from the cubes list, and then check if their sum is a perfect cube.

Here's an example of how you can modify your code using the combinations function:

import itertools
import numpy

cubes = [1, 8, 27, 64, 125]

# Generate all possible combinations of three items from the cubes list
combs = itertools.combinations(cubes, 3)

# Iterate over each combination
for comb in combs:
    # Check if the sum of the combination is a perfect cube
    s = sum(comb)
    if numpy.cbrt(s) == int(numpy.cbrt(s)):
        print(s)

This code will generate all possible combinations of three items from the cubes list and check if their sum is a perfect cube. The combinations function generates the combinations in a memory-efficient manner, so it should work for larger lists as well.

(Ugh... I just realized d doesn't have to be in the list, can be larger. So I'll need to extend this. Later...)

Solutions are cubes a < b < c < d with a + b + c == d. So d - c == a + b. Go through all pairs of c and d and check whether d - c occurs as a sum of some a and b. Takes about 0.01 seconds to solve the list of all cubes lower than 6'000'000.

from time import time

cubes = [i**3 for i in range(1, int(6e6**(1/3)) + 1)]

start = time()

a_plus_b = set()
sums = set()
for i, c in enumerate(cubes[2:], 2):
    b = cubes[i - 1]
    for a in cubes[:i-1]:
        a_plus_b.add(a + b)
    for d in cubes[i+1:]:
        if d - c in a_plus_b:
            sums.add(d)

print(time() - start)
print(sorted(sums))

Output (Attempt This Online!):

0.011432647705078125
[216, 729, 1728, 5832, 6859, 8000, 13824, 15625, 19683, 21952, 24389, 27000, 46656, 54872, 64000, 68921, 74088, 85184, 91125, 97336, 110592, 125000, 148877, 157464, 175616, 185193, 195112, 216000, 250047, 287496, 300763, 328509, 343000, 357911, 373248, 421875, 438976, 474552, 512000, 531441, 551368, 592704, 614125, 658503, 681472, 704969, 729000, 778688, 804357, 857375, 884736, 912673, 970299, 1000000, 1061208, 1092727, 1157625, 1191016, 1259712, 1331000, 1367631, 1404928, 1442897, 1481544, 1520875, 1560896, 1601613, 1728000, 1771561, 1815848, 1860867, 1953125, 2000376, 2048383, 2146689, 2299968, 2352637, 2406104, 2460375, 2571353, 2628072, 2685619, 2744000, 2803221, 2863288, 2985984, 3048625, 3176523, 3375000, 3442951, 3511808, 3581577, 3796416, 4019679, 4096000, 4251528, 4410944, 4657463, 4741632, 4913000, 5000211, 5088448, 5268024, 5359375, 5451776, 5545233, 5639752, 5735339, 5832000, 5929741]

Version showing all sums verbosely:

from collections import defaultdict

cubes = [i**3 for i in range(1, int(6e6**(1/3)) + 1)]

a_plus_b = defaultdict(list)
for i, c in enumerate(cubes[2:], 2):
    b = cubes[i - 1]
    for a in cubes[:i-1]:
        a_plus_b[a + b].append((a, b))
    for d in cubes[i+1:]:
        for a, b in a_plus_b[d - c]:
            print(f'{a} + {b} + {c} == {d}')

Output (Attempt This Online!):

27 + 64 + 125 == 216
1 + 216 + 512 == 729
216 + 512 + 1000 == 1728
729 + 1728 + 3375 == 5832
8 + 1728 + 4096 == 5832
343 + 2744 + 4913 == 8000
27 + 1000 + 5832 == 6859
1728 + 4096 + 8000 == 13824
5832 + 6859 + 9261 == 21952
64 + 4913 + 10648 == 15625
27 + 5832 + 13824 == 19683
3375 + 8000 + 15625 == 27000
1331 + 3375 + 19683 == 24389
5832 + 13824 + 27000 == 46656
64 + 13824 + 32768 == 46656
216 + 32768 + 35937 == 68921
2744 + 21952 + 39304 == 64000
9261 + 21952 + 42875 == 74088
216 + 8000 + 46656 == 54872
19683 + 27000 + 50653 == 97336
27 + 46656 + 50653 == 97336
8 + 4913 + 64000 == 68921
125 + 27000 + 64000 == 91125
13824 + 32768 + 64000 == 110592
4096 + 12167 + 68921 == 85184
46656 + 54872 + 74088 == 175616
512 + 39304 + 85184 == 125000
24389 + 39304 + 85184 == 148877
19683 + 46656 + 91125 == 157464
216 + 46656 + 110592 == 157464
3375 + 74088 + 117649 == 195112
27000 + 64000 + 125000 == 216000
9261 + 74088 + 132651 == 216000
1728 + 6859 + 148877 == 157464
729 + 27000 + 157464 == 185193
10648 + 27000 + 157464 == 195112
10648 + 132651 + 157464 == 300763
35937 + 85184 + 166375 == 287496
343 + 74088 + 175616 == 250047
343 + 157464 + 185193 == 343000
46656 + 110592 + 216000 == 373248
46656 + 54872 + 226981 == 328509
157464 + 185193 + 250047 == 592704
512 + 110592 + 262144 == 373248
125000 + 226981 + 262144 == 614125
39304 + 59319 + 274625 == 373248
59319 + 140608 + 274625 == 474552
54872 + 79507 + 287496 == 421875
1728 + 132651 + 287496 == 421875
1728 + 262144 + 287496 == 551368
21952 + 175616 + 314432 == 512000
6859 + 216000 + 328509 == 551368
195112 + 205379 + 328509 == 729000
2744 + 12167 + 343000 == 357911
74088 + 175616 + 343000 == 592704
29791 + 35937 + 373248 == 438976
1728 + 64000 + 373248 == 438976
729 + 157464 + 373248 == 531441
15625 + 110592 + 405224 == 531441
157464 + 216000 + 405224 == 778688
216 + 373248 + 405224 == 778688
21952 + 148877 + 421875 == 592704
91125 + 216000 + 421875 == 729000
17576 + 166375 + 474552 == 658503
54872 + 110592 + 493039 == 658503
8000 + 157464 + 493039 == 658503
91125 + 328509 + 493039 == 912673
64 + 39304 + 512000 == 551368
1000 + 216000 + 512000 == 729000
110592 + 262144 + 512000 == 884736
35937 + 91125 + 531441 == 658503
32768 + 97336 + 551368 == 681472
9261 + 79507 + 592704 == 681472
373248 + 438976 + 592704 == 1404928
32768 + 157464 + 614125 == 804357
42875 + 343000 + 614125 == 1000000
132651 + 314432 + 614125 == 1061208
15625 + 29791 + 636056 == 681472
4913 + 64000 + 636056 == 704969
15625 + 54872 + 658503 == 729000
1331 + 287496 + 681472 == 970299
4096 + 314432 + 681472 == 1000000
195112 + 314432 + 681472 == 1191016
3375 + 551368 + 704969 == 1259712
3375 + 125000 + 729000 == 857375
6859 + 148877 + 729000 == 884736
157464 + 373248 + 729000 == 1259712
35937 + 343000 + 778688 == 1157625
185193 + 438976 + 857375 == 1481544
1728 + 373248 + 884736 == 1259712
24389 + 421875 + 884736 == 1331000
125000 + 405224 + 912673 == 1442897
12167 + 636056 + 912673 == 1560896
636056 + 857375 + 912673 == 2406104
27000 + 592704 + 941192 == 1560896
5832 + 884736 + 970299 == 1860867
830584 + 884736 + 970299 == 2685619
216000 + 512000 + 1000000 == 1728000
6859 + 778688 + 1030301 == 1815848
1728 + 29791 + 1061208 == 1092727
74088 + 592704 + 1061208 == 1728000
117649 + 592704 + 1061208 == 1771561
2197 + 132651 + 1124864 == 1259712
2197 + 474552 + 1124864 == 1601613
250047 + 592704 + 1157625 == 2000376
12167 + 830584 + 1157625 == 2000376
729000 + 857375 + 1157625 == 2744000
13824 + 54872 + 1191016 == 1259712
4096 + 103823 + 1259712 == 1367631
5832 + 216000 + 1259712 == 1481544
85184 + 216000 + 1259712 == 1560896
85184 + 1061208 + 1259712 == 2406104
8000 + 614125 + 1331000 == 1953125
287496 + 681472 + 1331000 == 2299968
531441 + 729000 + 1367631 == 2628072
729 + 1259712 + 1367631 == 2628072
2744 + 592704 + 1404928 == 2000376
27 + 39304 + 1481544 == 1520875
2744 + 1259712 + 1481544 == 2744000
328509 + 778688 + 1520875 == 2628072
729 + 166375 + 1560896 == 1728000
85184 + 132651 + 1643032 == 1860867
117649 + 941192 + 1685159 == 2744000
216 + 132651 + 1728000 == 1860867
3375 + 729000 + 1728000 == 2460375
373248 + 884736 + 1728000 == 2985984
2197 + 274625 + 1771561 == 2048383
373248 + 438976 + 1815848 == 2628072
373248 + 614125 + 1815848 == 2803221
110592 + 328509 + 1860867 == 2299968
125 + 438976 + 1860867 == 2299968
54872 + 185193 + 1906624 == 2146689
328509 + 1860867 + 1906624 == 4096000
421875 + 1000000 + 1953125 == 3375000
9261 + 343000 + 2000376 == 2352637
1259712 + 1481544 + 2000376 == 4741632
85184 + 389017 + 2097152 == 2571353
4096 + 884736 + 2097152 == 2985984
1000000 + 1815848 + 2097152 == 4913000
314432 + 474552 + 2197000 == 2985984
474552 + 1124864 + 2197000 == 3796416
27 + 1771561 + 2248091 == 4019679
438976 + 636056 + 2299968 == 3375000
13824 + 1061208 + 2299968 == 3375000
658503 + 1061208 + 2299968 == 4019679
13824 + 2097152 + 2299968 == 4410944
166375 + 421875 + 2460375 == 3048625
531441 + 1259712 + 2460375 == 4251528
1728 + 531441 + 2515456 == 3048625
4913 + 1061208 + 2515456 == 3581577
175616 + 1404928 + 2515456 == 4096000
1225043 + 1259712 + 2515456 == 5000211
29791 + 262144 + 2571353 == 2863288
1 + 357911 + 2628072 == 2985984
357911 + 389017 + 2628072 == 3375000
54872 + 1728000 + 2628072 == 4410944
1 + 2460375 + 2628072 == 5088448
1560896 + 1643032 + 2628072 == 5832000
21952 + 97336 + 2744000 == 2863288
10648 + 421875 + 2744000 == 3176523
592704 + 1404928 + 2744000 == 4741632
884736 + 1225043 + 2803221 == 4913000
274625 + 658503 + 2863288 == 3796416
110592 + 2571353 + 2863288 == 5545233
238328 + 287496 + 2985984 == 3511808
13824 + 512000 + 2985984 == 3511808
5832 + 1259712 + 2985984 == 4251528
658503 + 1560896 + 3048625 == 5268024
328509 + 970299 + 3112136 == 4410944
91125 + 2000376 + 3176523 == 5268024
110592 + 2352637 + 3176523 == 5639752
97336 + 103823 + 3241792 == 3442951
205379 + 804357 + 3241792 == 4251528
125000 + 884736 + 3241792 == 4251528
175616 + 1191016 + 3375000 == 4741632
729000 + 1728000 + 3375000 == 5832000
1259712 + 1295029 + 3375000 == 5929741
6859 + 1481544 + 3511808 == 5000211
250047 + 2000376 + 3581577 == 5832000
21952 + 1685159 + 3652264 == 5359375
140608 + 1331000 + 3796416 == 5268024
438976 + 884736 + 3944312 == 5268024
64000 + 1259712 + 3944312 == 5268024
46656 + 185193 + 4019679 == 4251528
1728 + 636056 + 4019679 == 4657463
512 + 314432 + 4096000 == 4410944
8000 + 1728000 + 4096000 == 5832000
19683 + 729000 + 4251528 == 5000211
287496 + 729000 + 4251528 == 5268024
103823 + 912673 + 4251528 == 5268024
157464 + 512000 + 4330747 == 5000211
262144 + 778688 + 4410944 == 5451776
15625 + 778688 + 4657463 == 5451776
74088 + 636056 + 4741632 == 5451776
125000 + 238328 + 5088448 == 5451776
39304 + 512000 + 5088448 == 5639752
125000 + 438976 + 5268024 == 5832000
4913 + 185193 + 5545233 == 5735339