python - How can I avoid double checking in a brute force search? -

i saw post on reddit counterexample euler's conjecture. decided try brute force calculation myself.

my code

import numpy np  fifths1  = np.arange(1,151)  fifths = fifths1**5  x in fifths1:     y in fifths1:         z in fifths1:             w in fifths1:                  lambdas=[x,y,z,w]                  if sum(np.array(lambdas)**5) in fifths:                       print((x,y,z,w)) 

however, code takes long because triple checks cases.

from paper linked, counter example is

27^5 + 84^5 + 110^5 + 113^5 = 144^5 

my code returns

(27, 84, 110, 133) (27, 84, 133, 110) (27, 110, 84, 133) (27, 110, 133, 84) (27, 133, 84, 110) (27, 133, 110, 84) 

how can optimize brute force search not check same case multiple times.

i think numpy wrong library use here.

this isn't problem can vectorised in current form (the biggest reason use library) and, furthermore, looping on numpy arrays slower looping on python lists.

you incur performance penalty constructing new numpy array each time in inner loop , using in check sum (which o(n) in complexity).

as others have noted, itertools allows test each combination of 4 fifth-powers once. checking if sum of these powers fifth-power using set-membership (o(1) complexity) boost performance:

import itertools  fifths = [x**5 x in range(1, 151)] f_set = set(fifths)  [x x in itertools.combinations(fifths, 4) if sum(x) in f_set] 

which returns:

[(14348907, 4182119424, 16105100000, 41615795893)] 

and can recover fifth-roots (27, 84, 110, 133) there.