The City-Building Sequence A400000 by Visibility Thresholds: An Exact Level-Structure Algorithm

The city-building sequence A400000 is defined by a(1) = 0 and a(n) = the least height h of a building at position n that sees exactly h earlier buildings. We attach to every earlier building i a visibility threshold T_i(n), the lowest height from which it is seen, and prove: a(n) is the least h with at most h thresholds less than or equal to h; exactly a(n) stored slopes change in step n; and the thresholds of buildings with a non-negative stored slope never decrease. These facts give an exact algorithm that keeps the buildings in a ladder of levels ordered by threshold and never rescans the past. The algorithm is proved correct, with exact integer arithmetic and a proved double-precision filter. Its running time is bounded by explicit statistics of the sequence itself: the number E_N = sum_{n <= N} a(n) of visibility edges, the stack size B_n and the lengths of gaps between terms above a height h. On N = 3 * 10^7 terms the output agrees with an independent pruned-scan implementation and with the published terms and record indices. The measured time at N = 3 * 10^7 is 4.119 s against 12.698 s for the pruned scan, and in Python 0.102 s against 13.436 s for the published generator at N = 2 * 10^4.