自然数前段的均衡样本

hujunhua

又申请了6个序列，A390082~390087，
A390082，即127#中的d(n)的奇数项。
A390083，即127#中的d(n)的偶数项
A390084，既约平衡子集的最大长度，奇数项。我提交了14项，编辑给延长到了第50项。
A390085，既约平衡子集的最大长度，偶数项。我提交了14项，与其它三个既有序列还不能区分。

前面三个序列很快就通过了，第四个是本月3号提交的，今天才通过。因为我提交的项数不足以与既有的序列相区别。这一点在编辑时系统自动有警示，但我也没办法。现在问题没解决，先给通过了。

A390086， 打算给A390084的简并，即序列发生阶跃的地方.  
A390087， 打算给A390085的简并，即序列发生阶跃的地方.  

我没打算把A390082与A390083合并申请一个新的序列，也不打算合并A390084和A390085。

hujunhua

从127#开始，我们将自然数前段平移成了对称的零和整数集，例如自然数前段{1..2n+1}平移为{-n..n}。
随之，平衡样本转化成了零和整数集。
有关问题的阶段性结果包括：
1、{-n..n}有多少个本原零和子集，0~37项见A389803
2、{-n..n}有多少个完全划分？0~28项见A389806
3、{-n..n}包含 n 但不包含 -n的本原零和集有多少个，1~37项见A390082
     A390082就是A389803的向前差分，通过计算A390082，累计即得A389803。
4、{-n..n}的本原零和子集的最大长度，0~50项见A390084
     这是为编程计算问题3服务的。如果不考虑它而直接计算A390082(n)时，需要搜索的子集长度范围就是3~n, 但是观察A390084的前50项，显示A390084(n)≈`\sqrt{6n}`, 也就是在计算计算A390082(n)时，需要搜索的子集长度不超过`\sqrt{6n}`。当n较大时，这个差别就很大了。
5、n元本原零和集最小规模，也就是问题4的逆问题。1~16项见A390086

A390084的前50项：1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16
前0~14项是本论坛贡献的，第15~50项是OEIS的一位编辑贡献的。
忽略那些平台项，发生增长的项及相应的最长本原零和子集如下：
  a(0) = 1: {0}
  a(1) = 2: {-1, 1}
  a(3) = 3: ±{3, -2, -1}
  a(4) = 4: ±{4, -3, -2, 1}
  a(6) = 5: ±{6, -5, -4, 2, 1},
                  {6, -5, 4, -3, -2}
  a(8) = 6: ±{8, -7, 6, -5, -4, 2},
                  {8, -7, 5, -4, -3, 1}
  a(11) = 7: ±{11, 10, -9, -8, -7, 2, 1},
                    {11, -10, 9, -8, -7, 3, 2},
                    {11, -10, -9, 6, 5, -4, 1},
                    {11, -10, 8, -7, -6, 3, 1}
  a(14) = 8: ±{14, 13, -12, -11, -10, 3, 2, 1}（唯一）
  a(18) = 9: ±{18, 17, 16, -15, -14, -13, -12, 2, 1},
                    {18, 17, -16, 15, -14, -13, -12, 3, 2}
                    {18, 17, -16, -15, -14, 4, 3, 2, 1},
                    {18, -17, 13, -12, -11, 7, 6, -5, 1}
  a(21) = 10: ±{21, 20, 19, -18, -17, -16, -15, 3, 2, 1}（唯一）
  a(25) = 11: ±{25, 24, 23, -22, -21, -20, -19, 4, 3, 2, 1}
  a(30) = 12: ±{30, 29, 28, 27, -26, -25, -24, -23, -22, 3, 2, 1}
  a(34) = 13: ±{34, 33, 32, 31, -30, -29, -28, -27, -26, 4, 3, 2, 1}
  a(39) = 14: ±{39, 38, 37, 36, -35, -34, -33, -32, -31, 5, 4, 3, 2, 1}
  a(45) = 15: ±{45, 44, 43, 42, 41, -40, -39, -38, -37, -36, -35, 4, 3, 2, 1}
  a(50) = 16: ±{50, 49, 48, 47, 46, -45, -44, -43, -42, -41, -40, 5, 4, 3, 2, 1}

我们把它取反函数，就得到A390086，1~16项如下：0, 1, 3, 4, 6, 8, 11, 14, 18, 21, 25, 30, 34, 39, 45, 50
即 给定长度的本原零和整数集，它的最大元素(按绝对值）所能达到的最小值。观察这前16项，我们得到\[A390086(n)=\lfloor\frac{n(n+3)}6\rfloor=\begin{cases}\D\frac{n(n+3)}6, \text{ if }n\equiv0\\\D\frac{n(n+3)-4}6,\text{ if }n\neq0\end{cases}\pmod{3}\]
不过，上面的公式不是来自数据拟合，而是从上面观察到的最大子集构成模式中推导出来的。
从a(11)开始，最长子集具有{A~-B~C}的构成模式：\[A=\{a_k, ..., a_1\}, B=\{b_{k+1}, ..., b_1\}, C=\{c_m, ...,c_1\}\]
{A~B~C}按降序排列，并且 ∑A+∑C=∑B, `b_1`>∑C.
以下证明这种模式必是本原零和集。

hujunhua

假定它有较小的零和真子集{$A_1~B_1~C_1$}，($A_1, B_1, C_1$分别是 A, B, C 的一个子集），使得
        ∑`A_1`+∑`C_1`=∑`B_1`,  
       ` |A_1|+1≤|B_1|`, 因为 B 段的数较小嘛，得靠长度来平衡。
但是较小的零和真子集总是成对互补地出现，假定补集为{`A_1'~B_1'~C_1'`}, 使得
        ∑`A_1'`+∑`C_1'`=∑`B_1'`,  
       ` |A_1'|+1≤|B_1'|`
则 `|A_1|+|A_1'|+2≤|B_1|+|B_1'| → |A|+2 ≤ |B|`
这与 |A|+1=|B|相矛盾。

hujunhua

为了使 a_k尽可能小，A段, B 段, C 段都应该是连续整数段，B 段与 A 段宜接近， C 段的数字宜尽可能小，所以上述模式可以更具体
        {a, a-1, ..., a-k+1; -(a-k), -(a-k-1), ..., -(a-2k);c, c-1, ..., 1}
由零和可得
        (2a-k+1)k/2+c(c+1)/2=(2a-3k)(k+1)/2
给定长度为 n, 所以 2k+1+c = n, 将 c = n-2k-1 代入上式整理得
       a = 3k^2-(2n-3)k+n(n-1)/2
a为最小值，用差分代替微分，左边关于k的向前差分不大于0，向后差分不小于0， 即
       Δa(向前) = 3(2k-1)-(2n-3)≤0  → k≤n/3
       Δa(向后) = 3(2k+1)-(2n-3)≥0 → k≥n/3-1
所以，当 3|n时， $k = n/3 or n/3-1, c = n/3-1 or n/3+1, a = {n(n+3)}/6$
         当 3`\nmid`n时， `k =\D\lfloor\frac{n}3\rfloor, c=\lfloor\frac{n}3\rfloor+r-1,a=\frac{n(n+3)-4}6`
这里 r 是 n 除以 3 的余数。可见三段基本上是均长的。

由此可得 {-n..n}的本原零和子集的最大长度A390084(n)≈ `\sqrt{6n}`，准确一点，是$\sqrt{6n+25/4}-3/2$.

hujunhua

在127#，{1..2n} 被平移零和集{-n+½, -n+1+½, ..., -½, ½, ..., n-1-½, n-½},  乘以2后化整数为正负自对称的零和奇数集
       {-2n+1, -2n+3, ..., -1, 1, ...2n-3, 2n-1}
这个序列，本贴以后把它记为{-2n+1..2n-1, 2}
关于它的本原零和子集，有关进展如下：

1. {-2n+1..2n-1, 2}有多少个本原零和子集，1~30项见 A389804
2. {-2n+1..2n-1, 2}有多少个完全划分，1~14项见 A389807
3. {-2n+1..2n-1, 2}包含 2n-1 但不包含 -2n+1 的本原零和集有多少个，1~37项见A390083
     A390083就是A389804的向前差分，通过计算A390083，累计即得A389804。
4. {-2n+1..2n-1, 2}的本原零和子集的最大长度，1~30项见A390085
     这是为编程计算问题3服务的。如果不考虑它而直接计算A390083(n)时，需要搜索的子集长度范围就是4~n内的偶数. 但是既然A390084(n)可以缩减到$sqrt{6n}$, A390085(n)亦当如是。
5、n元本原零和集最小规模，也就是问题4的逆问题。1~16项见A390087

A390085的前30项：1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7
前1~14项是本论坛贡献的，第15~30项是OEIS的一位编辑贡献的。
忽略那些平台项，发生增长的项及相应的最长本原零和子集如下：
  a(1) = 1: {1, -1}
  a(4) = 2: {7, -5, -3, 1}
  a(6) = 3: {11, -9, 7, -5, -3, -1}
  a(11) = 4: {21, -19, 17, -15, 11, -7, -5, -3} (from Christian Sievers, Nov 12 2025)
                  {21, -19, 17, -15, -13, 5, 3, 1}
                  {21, 19, -17, 15, -13, -11, -9, -5}
  a(16) = 5: {31, 29, 27, -25, 23, -21, -19, -17, -15, -13}（唯一）
  a(23) = 6: {45, 43, 41, 39, -37, 35, -33, -31, -29, -27, -25, -21}（可能唯一）
  a(30) = 7: {59, 57, 55, 53, 51, -49, 47, -45, -43, -41, -39, -37, -35, -33}
我们把它取反函数，就得到A390087，1~7 项如下：1, 4, 6, 11, 16, 23, 30
即给定长度的本原零和奇数集，它的最大元素(按绝对值）所能达到的最小值。观察这前7项所带的最长子集，也提示了一个趋势：
1、n=2k 时，  A390087(n) = n(n+2)/2 - 1,   记 Δ = n(n+2)-3, 最长本原零和子集为{Δ, Δ-2, ..., Δ-2n+6, 2n-4-Δ, Δ-2n+2; 2n-Δ, 2n+2-Δ, ..., 4n-4-Δ,▊, 4n-Δ}，
2、n=2k-1时，A390087(n) = (n-1)(n+3)/2,   记 Δ = n(n+2)-4, 最长本原零和子集为{Δ, Δ-2, ..., Δ-2n+6, 2n-4-Δ, Δ-2n+2; 2n-Δ, 2n+2-Δ, ..., 4n-4-Δ, 4n-2-Δ}.
我们需要仿133#证明这两种零和子集对于较大的 n 恒为不可约零和集。
然后，还需要理解为什么最长子集是这种模式，为什么奇数长前段和偶数长前段的最长子集模式如此不同。

hujunhua

且将这种最长子集的正数部分记作$A={a_k, a_{k-1}, ..., a_1}$, 负数部分忽略负号记作$B={b_{k+2}, b_{k+1}, ..., b_1}$,
都是降序，两部分的大小有一处交叉: $a_2>b_{k+2}>a_1>b_{k+1}$.
假定它有成对互补的两个零和真子集{$A_1~B_1$}, {`A_1'~B_1'`}, (`A_1`, `B_1`分别是 A, B 的子集,  `A_1'`, `B_1'`是相应的补集), 使得
        ∑`A_1` = ∑`B_1`,   ∑`A_1'` = ∑`B_1'`
        2≤|`A_1`|, |`A_1'`|≤k-2, 2≤|`B_1`|, |`B_1'`|≤k,
        |`A_1`|+|`B_1`|是偶数 →|`B_1| - |A_1`|是偶数 →|`B_1|≥|A_1| +2`
同理  |`B_1'|≥|A_1'| +2`,  故 |`B_1|+|B_1'|≥|A_1| + |A_1’| +4`
即 |B|≥|A|+4, 这与 |B|=|A|+2相矛盾。

现在可以断言，A390085(n) ≤ $sqrt{2n+4}-1$