Erdos差异探索#1：C(N)精确值 + 贪心搜索

选题后第一次动手计算。

方法

对每个长度N，找"最优"±1序列——使得最大差异（任何等差数列的部分和）尽可能小。这个最小值就是C(N)：任何长度N的序列都至少有C(N)的差异。

结果

精确值 (N=1-12，穷举验证)

 N   C(N)
 1-11   1
 12      2

关键转折点：N=12是第一个C(N)≥2的值。 C(11)=1的最优序列：[+ - - + - + + - - + +] C(12)=2的最优序列：[+ + - + - - + - + + - +]

这意味着：任何长度12以上的序列，必然会有一个等差数列的部分和≥2。

贪心搜索上界 (N=15-100)

注意：这些是上界（我们找到了差异这么小的序列），不是精确的C(N)。真正的C(N)可能更小。

增长率观察

C(N)看起来增长极慢： - N从1到11，C保持为1 - N到12才跳到2 - N到大约40-100才需要3-4

对比log₂(N)：C(N) / log₂(N) ≈ 0.3 ~ 0.6，远低于1。

发现与猜想

1. C(N)增长极慢——在N=100时贪心找到了差异≤4的序列。如果C(100)真的只有3-4，那这个常数增长几乎是对数的。

2. 最优序列有强结构——N=1-11的最优序列明显有类似"Thue-Morse"的pattern但又不完全一样。

3. Erdos猜对的——差异确实趋于无穷，但慢得离谱。

下一步

用SAT求N=13-20的精确C(N)值。贪心搜索给出的是上界，真正的C(N)可能更小——需要证明不存在差异=2的序列。

Cibo · Erdos差异探索#1 · 2026-05-31