# A400000: the first 10^14 terms

This folder publishes the first 100 trillion (10^14) terms of OEIS **A400000**, the city-building sequence:

> a(n) is the least h such that a building of height h at position n sees exactly h of the earlier
> buildings (collinear rooftops count as visible).

Files:

| file | what it is |
|---|---|
| `A400000_100T.a4z` | a(1) … a(10^14) in one compressed file (16,455,776,321 bytes, about 16.5 GB) |
| `A400000_view.c` | the viewer: prints any range of terms, from the file or straight from its URL |
| `A400000_1T.c` | an independent generator: computes the terms from scratch (up to 4.4·10^12) |

SHA-256 of `A400000_100T.a4z`: `23782bd2751066fab21a2f4a4317cab25543126588d6f10866782bc2b584258d`

## Quick start

Build the viewer. It needs the zstd library.

```
# Linux (Debian/Ubuntu: apt install libzstd-dev; Fedora: dnf install libzstd-devel)
cc -O2 -o A400000_view A400000_view.c -lzstd

# macOS (brew install zstd)
cc -O2 -I/opt/homebrew/include -L/opt/homebrew/lib -o A400000_view A400000_view.c -lzstd

# no zstd library, but the zstd program is installed
cc -O2 -DUSE_ZSTD_CLI -o A400000_view A400000_view.c
```

Look at some terms:

```
./A400000_view A400000_100T.a4z                        # what the file holds
./A400000_view A400000_100T.a4z 1 100                  # a(1..100) as b-file lines "n a(n)"
./A400000_view A400000_100T.a4z 1e13 +20 -f c          # 20 terms from n = 10^13, comma-separated
./A400000_view A400000_100T.a4z 22433065737435         # a(22433065737435) = 314463, the tallest
./A400000_view A400000_100T.a4z 5e13 5e13+999999 -o b.txt   # a million terms into a b-file
./A400000_view A400000_100T.a4z records                # the records (A399949, A399950)
./A400000_view A400000_100T.a4z first 381              # where height 381 first appears (A399763)
./A400000_view A400000_100T.a4z sum 1e14               # a(1) + ... + a(10^14) (A397740)
```

You don't have to download the 16 GB file. Give the viewer the file's URL, and it fetches only the few hundred
kilobytes a query needs (it uses `curl` and HTTP range requests):

```
./A400000_view https://<this site>/files/A400000_100T.a4z 1e13 +20
```

## Commands

| command | prints |
|---|---|
| `info` (default) | number of terms, sum, hash, largest term, number of distinct heights and records |
| `N` | a(N) |
| `A B` | a(A..B); B can be `+K` for K terms |
| `sum N` | a(1) + … + a(N), A397740(N) |
| `records` | each record height and its index (A399949, A399950) |
| `first H` | the index of the first building of height H (A399763) |
| `heights` | every height that occurs, with its first index and its number of occurrences |
| `verify [A B]` | decompresses the chunks holding a(A..B) (default: all) and checks them against the index |

Formats: `-f b` b-file lines `n a(n)` (default), `-f c` comma-separated, `-f v` values only. `-o FILE`
writes to a file. Numbers can be written as `123`, `1e13`, `2^40`, `1e13+5`, `2^40-1`.

A query decompresses the 2^31-term chunks it touches: up to about a second and about 1 GB of memory per chunk.
Printing is the slow part of a long range (a b-file is about 15 bytes per term).

## How the file is organized

The archive's 46,567 chunks each hold 2^31 consecutive terms, except the last, which holds 276,447,232. Each chunk
stores one byte per term (escape codes for terms ≥ 255) and is compressed as a single zstd frame. Before the chunks
come a plain-text description (the first 4,096 bytes), a header, an index, and two small tables: every height with
its first index and count, and the records. The index stores each chunk's position and size, plus the running sum
and the running FNV-1a hash of all terms up to the chunk's end, so any chunk can be checked on its own. The exact
layout is documented at the top of `A400000_view.c`.

The sequence compresses about 6,000 to 1 because it repeats itself. After each tall building the city starts over,
and long stretches of terms recur exactly.

## How the terms were computed and checked

* **Computation.** A single sequential run on a Mac Studio (Apple M2 Ultra) took about 2.6 days (2026-10-26 to 2026-10-29), at about 2.2 ns per
  term. It uses R. Sigrist's sight-line method, accelerated by tiers of sight lines, memoized replay of the runs
  between tall buildings, and exact 64-bit/128-bit integer arithmetic. `A400000_1T.c` is that program for
  n < 2^42, as one file with all the optimizations explained.
* **Independent recomputation.** Every term was recomputed by a second program with the memoization switched off,
  segment by segment, on four other machines. Each recomputed term was compared with the stored one. @VERIFIED@
* **Agreement with the OEIS.** The archive agrees with every term published in the OEIS b-files of A400000 and of
  the sequences derived from it (A399763, A397493, A400121, A399949, A399950, A397740, …).
* **Internal checks.** `verify` reproduces each chunk's terms, sum and running FNV-1a hash from the index, which
  was taken from the generator's log. The complete file passed this check (all 46,567 chunks) before release. The hash is h = 0xcbf29ce484222325, then h = (h XOR a(n)) · 0x100000001b3
  mod 2^64 for n = 1, 2, …. The program `A400000_1T.c` recomputes the terms from scratch and checks the same hashes
  at 2^30, 2^31, …, so anyone can confirm the start of the file independently.

Some numbers from the first 10^14 terms: the tallest building is a(22433065737435) = 314463. There are 29 records
and 2342 distinct heights. The smallest height that does not occur is 657. The sum of all terms is 293509519875334.
