求{1, 2, ..., 100}没有等和对的最大子集
求{1, 2, ..., 100}的最大子集，使得没有等和2元子集。比如子集{1,2,4,8,16,32,64}的C(7,2)=21个2元子集，各子集的和显然两两不等。但这不一定是长度最大的子集。
实际上要的并不是各个最大子集，而是最大子集的长度值，这才是唯一的。有趣的问题，难得的数据 且记最大子集的长度为a(100), 不过100的规模太大了, 先从小数试起。
a(1)=1
a(2)=2
a(3)=3
a(4)=3
a(5)=4, {5,4,3,1}, {5,3,2,1}
a(6)=4, {6,5,4,2}, {6,4,3,2}, {6,5,4,1}
a(7)=4, {7,6,5,3}, ...
a(8)=5, {8,7,6,4,1}, ...
a(9)=5, {9,8,7,5,2}, ...
a(10)=5, {10,9,8,6,3}, ...
a(11)=5, {11,10,9,7,4}, ...
a(12)=5, {12,11,10,8,5}, ...
a(13)=6, {13,12,11,9,6,1}, ...
a(14)=6, {14,13,12,10,7,2}, ...
a(15)=6, {15,14,13,11,8,3}, ...
a(16)=6, {16,15,14,12,9,4}, ...
a(17)=6, {17,16,15,13,10,5}, ...
a(18)=6, {18,17,16,14,11,6}, ...
a(19)=6, {19,18,17,15,12,7}, ...
a(20)=6, {20,19,18,16,13,8}, ...
a(21)=7, {21,20,19,17,14,9,1}, ...
a(22)=7, {22,21,20,18,15,10,2}, ...
a(23)=7, {23,22,21,19,16,11,3}, ...
a(24)=7, {24,23,22,20,17,12,4}, ...
a(25)=7, {25,24,23,21,18,13,5}, ...
a(26)=7, {26,25,24,22,19,14,6}, ...
a(27)=7, {27,26,25,23,20,15,7}, ...
a(28)=7, {28,27,26,24,21,16,8}, ...
a(29)=7, {29,28,27,25,22,17,9}, ...
a(30)=8, {30,29,28,26,23,18,10,1}, ...
a(31)=8, {31,30,29,27,24,19,11,2}, ...
a(32)=8, {32,31,30,28,25,20,12,3}, ...
a(33)=8, {33,32,31,29,26,21,13,4}, ...
a(34)=8, {34,33,32,30,27,22,14,5}, ...
a(35)=8, {35,34,33,31,28,23,15,6}, ...
a(36)=8, {36,35,34,32,29,24,16,7}, ...
a(37)=8, {37,36,35,33,30,25,17,8}, ...
a(38)=8, {38,37,36,34,31,26,18,9}, ...
a(39)=9, {39,38,37,35,32,27,19,10}, ...
a(40)=9, {39,38,37,35,32,27,19,10}, ... 这个序列可以简并压缩，通过提取其中相同长度的项数。如果2楼的结果是正确的，那么这个序列就是
1, 1, 2, 3, 5, 8, 9, 9, ... A260998: Maximal size of a subset of Z_n with distinct sums of pairs (of distinct elements).
1, 2, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10
有点相似但又不同。可能它的 Z_n 是同余系？
特别是它的序列还出现一处小小的波动 8, 7, 8, 好奇怪哦。看了列出的前254项，坡处都有小波动。
按我们的定义，a(n)是单调递增的，不可能出现波动。 我们把{1,2,3,...,100}前移变为{0,1,2,...,99}, 将2#中的最大子集改为它的对称集，排算到100，结果如下：
a(4)= 3, {0,1,2},
a(5)= 4, {0,1,2,4},
a(6)= 4, {0,1,2,4},
a(7)= 4, {0,1,2,4},
a(8)= 5, {0,1,2,4,7},
a(9)= 5, {0,1,2,4,7},
a(10)= 5, {0,1,2,4,7},
a(11)= 5, {0,1,2,4,7},
a(12)= 5, {0,1,2,4,7},
a(13)= 6, {0,1,2,4,7,12},
a(14)= 6, {0,1,2,4,7,12},
a(15)= 6, {0,1,2,4,7,12},
a(16)= 6, {0,1,2,4,7,12},
a(17)= 6, {0,1,2,4,7,12},
a(18)= 6, {0,1,2,4,7,12},
a(19)= 6, {0,1,2,4,7,12},
a(20)= 6, {0,1,2,4,7,12},
a(21)= 7, {0,1,2,4,7,12,20},
a(22)= 7, {0,1,2,4,7,12,20},
a(23)= 7, {0,1,2,4,7,12,20},
a(24)= 7, {0,1,2,4,7,12,20},
a(25)= 7, {0,1,2,4,7,12,20},
a(26)= 7, {0,1,2,4,7,12,20},
a(27)= 7, {0,1,2,4,7,12,20},
a(28)= 7, {0,1,2,4,7,12,20},
a(29)= 7, {0,1,2,4,7,12,20},
a(30)= 8, {0,1,2,4,7,12,20,29},
a(31)= 8, {0,1,2,4,7,12,20,29},
a(32)= 8, {0,1,2,4,7,12,20,29},
a(33)= 8, {0,1,2,4,7,12,20,29},
a(34)= 8, {0,1,2,4,7,12,20,29},
a(35)= 8, {0,1,2,4,7,12,20,29},
a(36)= 8, {0,1,2,4,7,12,20,29},
a(37)= 8, {0,1,2,4,7,12,20,29},
a(38)= 8, {0,1,2,4,7,12,20,29},
a(39)= 9, {0,1,2,4,7,12,20,29,38},
a(40)= 9, {0,1,2,4,7,12,20,29,38},
a(41)= 9, {0,1,2,4,7,12,20,29,38},
a(42)= 9, {0,1,2,4,7,12,20,29,38},
a(43)= 9, {0,1,2,4,7,12,20,29,38},
a(44)= 9, {0,1,2,4,7,12,20,29,38},
a(45)= 9, {0,1,2,4,7,12,20,29,38},
a(46)= 9, {0,1,2,4,7,12,20,29,38},
a(47)= 9, {0,1,2,4,7,12,20,29,38},
a(48)= 9, {0,1,2,4,7,12,20,29,38},
a(49)= 9, {0,1,2,4,7,2,20,29,38},
a(50)= 9, {0,1,2,4,7,12,20,29,38},
a(51)= 9, {0,1,2,4,7,12,20,29,38},
a(52)= 9, {0,1,2,4,7,12,20,29,38},
a(53)= 10, {0,1,2,4,7,12,20,29,38,52},
a(54)= 10, {0,1,2,4,7,12,20,29,38,52},
a(55)= 10, {0,1,2,4,7,12,20,29,38,52},
a(56)= 10, {0,1,2,4,7,12,20,29,38,52},
a(57)= 10, {0,1,2,4,7,12,20,29,38,52},
a(58)= 10, {0,1,2,4,7,12,20,29,38,52},
a(59)= 10, {0,1,2,4,7,12,20,29,38,52},
a(60)= 10, {0,1,2,4,7,12,20,29,38,52},
a(61)= 10, {0,1,2,4,7,12,20,29,38,52},
a(62)= 10, {0,1,2,4,7,12,20,29,38,52},
a(63)= 10, {0,1,2,4,7,12,20,29,38,52},
a(64)= 10, {0,1,2,4,7,12,20,29,38,52},
a(65)= 10, {0,1,2,4,7,12,20,29,38,52},
a(66)= 10, {0,1,2,4,7,12,20,29,38,52},
a(67)= 10, {0,1,2,4,7,12,20,29,38,52},
a(68)= 10, {0,1,2,4,7,12,20,29,38,52},
a(69)= 10, {0,1,2,4,7,12,20,29,38,52},
a(70)= 10, {0,1,2,4,7,12,20,29,38,52},
a(71)= 10, {0,1,2,4,7,12,20,29,38,52},
a(72)= 10, {0,1,2,4,7,12,20,29,38,52},
a(73)= 10, {0,1,2,4,7,12,20,29,38,52},
a(74)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(75)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(76)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(77)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(78)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(79)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(80)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(81)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(82)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(83)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(84)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(85)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(86)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(87)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(88)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(89)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(90)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(91)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(92)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(93)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(94)= 11, {0,1,2,4,7,12,20,29,38,52,73},
a(95)= 12, {0,1,2,4,7,12,20,29,38,52,73,94},
a(96)= 12, {0,1,2,4,7,12,20,29,38,52,73,94},
a(97)= 12, {0,1,2,4,7,12,20,29,38,52,73,94},
a(98)= 12, {0,1,2,4,7,12,20,29,38,52,73,94},
a(99)= 12, {0,1,2,4,7,12,20,29,38,52,73,94},
a(100)= 12, {0,1,2,4,7,12,20,29,38,52,73,94}
找到A010672：A B_2 sequence: a(n) = least value such that the sequence increases and pairwise sums of distinct terms are all distinct.
0, 1, 2, 4, 7, 12, 20, 29, 38, 52, 73, 94, 127, 151, 181, 211, 257, 315, 373, 412, 475, 530, 545, 607, 716, 797, 861, 964, 1059, 1160, 1306, 1385, 1434, 1555, 1721, 1833, 1933, 2057, 2260, 2496, 2698, 2873, 3060, 3196, 3331, 3628, 3711, 3867, 4139, 4446, 4639 王守恩 发表于 2025-7-2 07:31
我们把{1,2,3,...,100}前移变为{0,1,2,...,99}, 将2#中的最大子集改为它的对称集，排算到100，结果如下：
...如果保持{1, 2, 3, ..., 100}, 不把首数前移为0，那么对应的序列为A011185：
{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, 2874, 3061, 3197, 3332, 3629, 3712,...}
A011185没有通项公式——我来补一个——虽然很丑。
seq = {0};pairSums = {};nextTerm = 1;pairSumsUpdate := JoinhasDuplicates := !
DuplicateFreeQDo;pairSums = pairSumsUpdate;AppendTo;, 50]seq + 1 A010672的差分
1, 1, 2, 3, 5, 8, 9, 9, 14, 21, 21, 33, 24, 30, 30, 46, 58, 58, 39, 63, 55, 15, 62, 109, 81, 64, 103, 95, 101, 146, 79, 49, 121, 166, 112, 100, 124, 203, 236, 202, 175, 187, 136, 135, 297, 83, 156, 272, 307, 193
即3#中所说的那个简并序列。这个序列不是递增的，有点出乎意料。 题目是 aimisiyou的——从1~100中至少选出多少个不同的数，必然存在四个不同的数，满足a+b=c+d? 备忘——记录一下手工解题的过程。
求{1, 2, ..., n}没有等和对的最大子集a(k),n>3。
a(3)=3, {1,2,3}——每次只要关注末尾2个数之间数是否有解就可以了。譬如:
a(4)=5, {1,2,3,5}——3,5之间有4——1,2,3,4有解。
a(5)=8, {1,2,3,5,8}——5,8之间有6,7——1,2,3,5,6-1,2,3,5,7有解。
a(6)=13, {1,2,3,5,8,13}——8,13之间有9,10,11,12——1,2,3,5,8,9-1,2,3,5,8,12有解。
a(7)=21, {1,2,3,5,8,13,21}——13,21之间有14-20——1,2,3,5,8,13,14-1,2,3,5,8,13,20有解。
a(8)=30, {1,2,3,5,8,13,21,30}——21,30之间有22-29——1,2,3,5,8,13,21,22-1,2,3,5,8,13,21,29有解。
a(9)=39, {1,2,3,5,8,13,21,30,39}——30,39之间有31-38——1,2,3,5,8,13,21,30,31-1,2,3,5,8,13,21,38有解。
a(10)=53, {1,2,3,5,8,13,21,30,39,53}
a(11)=74, {1,2,3,5,8,13,21,30,39,53,74},
a(12)=95, {1,2,3,5,8,13,21,30,39,53,74,95},
得到——A011185——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, ......
这个通项公式也可以。
t = {1}; k = 1; sms = {}; Do != {}, k++]; sms = Join; AppendTo, {50}]; t
又：{1, 2, ..., n}没有等和对的最大子集a(k)可以有很多数字串——只要把这个"A"换一下就行。
t = {1}; k = 1; sms = {}; Do != {}, k++]; sms = Join; AppendTo, {50}]; t Depth:7
1 2 3 5 9 14 19
Depth:7
1 2 3 8 11 15 19
Depth:7
1 5 9 12 17 18 19
Depth:7
1 6 11 15 17 18 19