对总和为五次方的四个五次方进行强力搜索的 python 脚本

Question

在下面的问题中，我试图编写一个 python 脚本，该脚本对总和为五次方的四个五次方进行强力搜索。因此我试图找到数字 a1、a2、a3、a4、a5 使得 a1^5+a2^5+a3^5+a4^5=a5^5

此搜索的范围是 Nmin=20 和 Nmax=200。 Nmin <= a1 < a2 < a3 < a4 < a5 <= Nmax。所以每个数字都必须小于之前的数字，并且它们必须在 20 到 200 之间。

import numpy as np

b  = np.arange(20,201)
a = b**5

for x in b:
    for y in b:
        for z in b:
            for w in b:

                lambdas=[x,y,z,w]

                if sum(np.array(lambdas)**5) in a:
                    print((x,y,z,w))

给出以下输出:

(20, 64, 128, 192)
(20, 64, 192, 128)
(20, 128, 64, 192)
(20, 128, 128, 128)
(20, 128, 192, 64)
(20, 192, 64, 128)
(20, 192, 128, 64)

所以这是错误的输出，我应该得到以下信息:

(27, 84, 110, 133)

好像没有考虑到a1 < a2 < a3 < a4 < a5。我正在寻找修复此代码的帮助!不试图让它更高效和运行得更快只是试图得到正确的答案

Answer 1

你看过a了吗？您可能会看到类似这样的内容:

In [3]: a
Out[3]: 
array([    3200000,     4084101,     5153632,     6436343,     7962624,
           9765625,    11881376,    14348907,    17210368,    20511149,
          24300000,    28629151,    33554432,    39135393,    45435424,
          52521875,    60466176,    69343957,    79235168,    90224199,
         102400000,   115856201,   130691232,   147008443,   164916224,
         184528125,   205962976,   229345007,   254803968,   282475249,
         312500000,   345025251,   380204032,   418195493,   459165024,
         503284375,   550731776,   601692057,   656356768,   714924299,
         777600000,   844596301,   916132832,   992436543,  1073741824,
        1160290625,  1252332576,  1350125107,  1453933568,  1564031349,
        1680700000,  1804229351,  1934917632,  2073071593, -2075960672,
       -1921920421, -1759441920, -1588183139, -1407792928, -1217910897,
       -1018167296,  -808182895,  -587568864,  -355926653,  -112847872,
         142085829,   409302880,   689241911,   982351872,  1289092153,
        1609932704,  1945354155, -1999119360, -1633050899, -1250894368,
        -852125217,  -436207616,    -2594335,   449273376,   919965907,
        1410065408,  1920165909, -1844093856, -1292161145,  -718372864,
        -122086263,   497353888,  1140615419,  1808378880, -1793629635,
       -1074769184,  -329287633,   443547648,  1244482609,  2074276640,
       -1361264605,  -471419904,   449643877,  1402741088, -1906267177,
        -886603776,   167620825,  1257277856, -1911714229,  -748520448,
         452807053,  1693198304, -1321368961,           0,  1363313281,
       -1525405664,   -75216013,  1419936768, -1333877067,   254330464,
        1890661415,  -718766080,  1017084201, -1490604384,   349237147,
       -2052174848,  -103738147,  1900764384,  -332433201,  1787822080,
        -327168815,  1913781536,   -77991229, -2006232064,   425331717,
       -1371911328,  1193314423,  -467566592, -2058209927,   717747104,
        -728216341, -2099700736,   899712045,  -318443040, -1457710305,
        1778384896,   801434401,   -92048864,  -900499949, -1622334464,
        2039018837,  1495248992,  1042966727,   683835392,   419538377,
         251779232,   182281787,   212790272,   345069437,   580904672,
         922102127,  1370488832,  1927912817, -1698724064,  -917596829,
         -21761024,   990716581,  2121790816,  -921529065,   452689920,
        1951500825,  -718021216,  1036123019, -1373914112,   643911373,
       -1498203168,   791831487, -1073741824,  1497211841,   -83018720,
       -1517219661,  1491846144,   356537333,  -625862048, -1453011609,
       -2122547200], dtype=int32)

你可以看到负数的地方，这是因为 int32 的类型不够大，无法处理所有数字的五次方:

In [4]: np.iinfo(np.int32)
Out[4]: iinfo(min=-2147483648, max=2147483647, dtype=int32)

但是

In [104]: np.iinfo(np.int64)
Out[104]: iinfo(min=-9223372036854775808, max=9223372036854775807, dtype=int64)

这就足够了。

所以，如果我切换到

b = np.arange(20,201, dtype=np.int64)

和

np.array(lambdas, dtype=np.int64)

然后我得到

(27, 84, 110, 133)

如预期。

(优化点 #1:如果您使用 itertools.combinations，您不仅不必嵌套循环，而且速度会快得多，因为您不需要查找数字。

优化点 #2:当 a 是一个数组时，in a 可能会非常慢，因为它必须扫描整个列表。如果将 a 设为集合，则成员资格测试几乎是即时的。)