求{1, 2, ..., 100}没有等和对的最大子集

mathe

1 2 3 5 9 15 20 25
1 2 3 5 9 16 25 30 35
1 2 8 11 14 22 27 42 44 46
然后可以找到 https://oeis.org/A345731

王守恩

接9#：{1, 2, ..., n}没有等和对的最大子集a(k)可以有很多数字串——只要把这个"A"换一下就行。这个公式速度极快, 也许调一调功能会更好——可惜我不会调。

1. Table[t = {1}; k = 1; sms = {}; Do[k++; While[Intersection[sms, k + t] != {}, k++]; sms = Join[sms, t + k, { A k}]; AppendTo[t, k], {40}]; t , {A, 9}]

复制代码

{1, 2, 3, 5, 8, 13, 21, 30, 39, 53, 74, 95, 128, 152, 182, 212, 258, 316, 374, 413, 476, 531, 546, 608, 717, 798, 862, 965, 1060, 1161, 1307, 1386, 1435, 1556, 1722, 1834, 1934, 2058, 2261, 2497, 2699},
{1, 2, 4, 8, 13, 21, 31, 45, 66, 81, 97, 123, 148, 182, 204, 252, 290, 361, 401, 475, 565, 593, 662, 775, 822, 916, 970, 1016, 1159, 1312, 1395, 1523, 1572, 1821, 1896, 2029, 2254, 2379, 2510, 2780, 2925},
{1, 2, 3, 9, 12, 16, 21, 37, 53, 70, 92, 115, 139, 163, 192, 235, 307, 363, 394, 451, 491, 572, 599, 637, 697, 771, 866, 1006, 1115, 1141, 1272, 1335, 1499, 1763, 1845, 1887, 2098, 2128, 2316, 2517, 2738},
{1, 2, 3, 8, 12, 15, 23, 38, 55, 71, 87, 105, 132, 160, 198, 240, 279, 298, 323, 374, 486, 510, 584, 675, 716, 803, 919, 1018, 1083, 1233, 1401, 1540, 1636, 1724, 1865, 2087, 2193, 2366, 2499, 2606, 2773},
{1, 2, 3, 5, 11, 16, 21, 28, 40, 61, 82, 110, 144, 174, 196, 218, 259, 306, 378, 424, 515, 583, 670, 723, 766, 844, 992, 1076, 1173, 1268, 1299, 1374, 1521, 1611, 1709, 1939, 2068, 2168, 2320, 2538, 2840},
{1, 2, 3, 5, 8, 14, 23, 31, 39, 55, 74, 88, 132, 171, 210, 250, 277, 332, 387, 435, 481, 491, 593, 655, 731, 806, 881, 981, 1096, 1159, 1276, 1418, 1509, 1630, 1769, 1883, 2036, 2270, 2375, 2521, 2813},
{1, 2, 3, 5, 8, 14, 22, 36, 46, 61, 86, 109, 135, 161, 177, 223, 253, 280, 345, 431, 485, 536, 613, 674, 783, 812, 929, 947, 1132, 1214, 1293, 1362, 1504, 1597, 1778, 1976, 2096, 2133, 2360, 2396, 2602},
{1, 2, 3, 5, 8, 17, 25, 33, 43, 54, 81, 100, 136, 169, 202, 241, 286, 331, 390, 437, 533, 546, 607, 717, 761, 900, 987, 1057, 1119, 1210, 1328, 1465, 1542, 1707, 1767, 1880, 2004, 2184, 2339, 2546, 2803},
{1, 2, 3, 5, 8, 14, 23, 33, 41, 57, 74, 91, 120, 149, 194, 229, 276, 290, 343, 419, 442, 520, 582, 624, 689, 799, 890, 949, 1013, 1146, 1244, 1325, 1561, 1646, 1797, 1841, 1936, 2104, 2263, 2311, 2642}}

hujunhua

mathe 发表于 2025-7-3 15:51
1 2 3 5 9 15 20 25
1 2 3 5 9 16 25 30 35
1 2 8 11 14 22 27 42 44 46

一直怀疑9#的贪心算法得到的局部最优解不是全局最优解，果然。

穷搜算法随着规模增长计算量呈指数级增长，目前只计算到第17项可以理解。

我没有编程穷搜，是因为觉得以我的机器配置，可能算不了几项

mathe

https://arxiv.org/pdf/2103.15850