A400000：无限的城市建造序列，每个数都会出现吗？

什么是 A400000？定义、前几项和惊人的规模

我第一次看到 A400000 这个编号时，心里想的是，OEIS 的条目已经超过四十万条了，一条新序列要在这堆数字里冒头，总得有点特别的地方。它的名字叫“城市建造序列”（city-building sequence），定义是：a(n) 等于高度 h 的最短建筑，这栋建筑恰好能看到 h 座更早的建筑。来源：OEIS

前几项是 0, 1, 1, 2, 1, 2, 1, 3, 1, 2, 1, 3, 1, 2, 1, 10, 1, 2, 2, 3, ... 来源：OEIS。一眼看去，大部分项都很小，1 和 2 反复出现，像是某种规律性很强的振荡。但仔细看，第 16 项突然跳到 10，然后隔了一段又是 10、11、10、11、10、19 这样的尖峰。这些尖峰出现在 n = 16k（k = 1..7）的位置，对应值分别是 10, 10, 11, 10, 11, 10, 19，和 n = 2 到 8 的初始模式 1, 1, 2, 1, 2, 1, 3 形状相似，只是被放大了一些。来源：OEIS

“看见”在这里有严格定义。建筑 a(j) 能看到更早的建筑 a(i)，当且仅当所有中间建筑 a(k)（i < k < j）的顶部都落在或低于连接 (i, a(i)) 和 (j, a(j)) 的直线上。来源：OEIS 换句话说，你站在 j 的位置往左看，视线不能被任何更高的楼挡住。这个几何条件决定了每一项的取值。

规模上，这个序列已经被计算到至少 2,300,000,000 项，也就是 23 亿项。来源：OEIS 我见过不少 OEIS 序列在几万项就停下来了，因为计算变得太慢或者模式已经确认。23 亿项意味着这个序列的计算过程本身就有意思，不只是定义好看。

证明与反直觉发现：序列无限，但每个数会出现吗？

定义本身没有保证序列能无限延续。每个位置都要找一个满足条件的高度 h，如果某一步找不到，序列就在那里终止。这是 A400000 最反直觉的地方：它看起来像一个可能随时断掉的序列，但 Rémy Sigrist 在 2026 年 9 月 16 日给出了一个证明，表明序列是无限的。来源：OEIS

证明的思路是这样的。假设我们已经有了前 n 项，要决定 a(n+1) 的值。定义 v(k) 为从位置 n+1、高度 k 处能看到的前 n 座建筑的数量。v(0) 大于 0，因为从地面能看到位置 n 那栋建筑；v(k) = n 对足够大的 k 成立，因为从足够高处能看到所有楼；v(k)