求{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

aimisiyou

最小子集呢？

王守恩

aimisiyou 发表于 2025-7-8 10:11
最小子集呢？

最小子集——A345731——1, 2, 4, 7, 12, 18, 24, 34, 45, 57, 71, 86, 105, 126, 150, 171,——目前只计算到第17项可以理解。

12#的公式，速度极快——也许调一调——能把第18项计算出来——看来是痴心妄想。

题目——从1~100中至少选出多少个不同的数，必然存在四个不同的数，满足a+b=c+d?

答案——从1~100中至少选出14个不同的数，必然存在四个不同的数，满足a+b=c+d。

思路: 从1~100中选出13个不同的数——不满足a+b=c+d——只要再加1个(剩下数中的任意1个)——就满足a+b=c+d。

从1~100中可以选出13个不同的数——参考A345731——每个数+1——2, 3, 5, 8, 13, 19, 25, 35, 46, 58, 72, 87,

注意:这13个数——肯定不是这13个数——1, 2, 3, 5, 8, 13, 19, 25, 35, 46, 58, 72, 87——是那13个数？——我还没有找到。

aimisiyou

王守恩 发表于 2025-7-8 16:53
最小子集——A345731——1, 2, 4, 7, 12, 18, 24, 34, 45, 57, 71, 86, 105, 126, 150, 171,——目前只计 ...

{19,38,50,64,65,68,73,75,81}再任意添加一个，就必然满足a+b=c+d,那么此时至少选10个数。

王守恩

aimisiyou 发表于 2025-7-8 20:22
{19,38,50,64,65,68,73,75,81}再任意添加一个，就必然满足a+b=c+d,那么此时至少选10个数。 ...

{1, 2, 3, 05, 09, 16, 25, 30, 35}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选10个数。
{1, 2, 8, 11, 14, 22, 27, 42, 44, 46}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选11个数。
{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选12个数——还没有找到。
{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选13个数——还没有找到。
{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72, 87}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选14个数——还没有找到。

aimisiyou

王守恩 发表于 2025-7-9 04:06
{1, 2, 3, 05, 09, 16, 25, 30, 35}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选10个数。
{1, 2, 8 ...

我说的是1～100范围内。

王守恩

说得透一些。
1～(03—04)范围——{1, 2, 3}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选4个数。
1～(05—07)范围——{1, 2, 3, 05}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选5个数。
1～(08—12)范围——{1, 2, 3, 05, 08}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选6个数。
1～(13—18)范围——{1, 2, 3, 05, 08, 13}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选7个数。
1～(19—24)范围——{1, 2, 3, 05, 09, 14, 19}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选8个数。
1～(25—34)范围——{1, 2, 3, 05, 09, 15, 20, 25}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选9个数。
1～(35—45)范围——{1, 2, 3, 05, 09, 16, 25, 30, 35}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选10个数。
1～(46—57)范围——{1, 2, 8, 11, 14, 22, 27, 42, 44, 46}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选11个数。
1～(58—71)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选12个数——还没有找到。
1～(72—86)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选13个数——还没有找到。
1～(87—105)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72, 87}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选14个数——还没有找到。
1～(106—126)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72, 87,106}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选15个数——还没有找到。
1～(127—150)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72, 87,106,127}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选16个数——还没有找到。
1～(151—171)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72, 87,106,127,151}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选17个数——还没有找到。
1～(172—？？)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72, 87,106,127,151,172}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选18个数——？？？？。
1～(？？—？？)范围——{1, 2, 3, 05, 08, 13, 19, 25, 35, 46, 58, 72, 87,106,127,151,172,？？}再任意添加一个, 就必然满足a+b=c+d, 那么此时至少选19个数——？？？？。

最小子集——A345731——1, 2, 4, 7, 12, 18, 24, 34, 45, 57, 71, 86, 105, 126, 150, 171,——目前只计算到第17项可以理解。