OEIS A400000 · a(1) to a(1014)

Data & tools

All hundred trillion terms in one 16.5 GB file. A small program prints any part of it: one term, a range, a b-file of a billion terms, the records, or where each height first appears. It works on a downloaded copy, or straight from this site's URL without downloading the whole file.

Files

filesizewhat it is
A400000_100T.a4z16.46 GBa(1), …, a(1014): 46,567 compressed chunks of 231 terms, with an index (A4Z format)
A400000_view.c29 KBthe viewer: prints any range of terms from the file or its URL (C, needs the zstd library)
A400000_1T.c87 KBa generator: computes the terms from scratch, about 1.6 ns per term, for n < 242; one commented file with every optimization explained
README.md5 KBthese notes as plain text, to go with the files
SHA256SUMS.txtSHA-256 checksums of the files above
b-filesOEIS b-files for A400000 and the sequences derived from it (below)

SHA-256 of A400000_100T.a4z: 23782bd2751066fab21a2f4a4317cab25543126588d6f10866782bc2b584258d

Quick start

Build the viewer. It needs the zstd compression library, which most systems have as a package.

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

# macOS (with Homebrew: 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

Then ask it for terms. A query reads only the 231-term chunks it touches, so it answers in about a second.

./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           # one term: the tallest building, 314463
./A400000_view A400000_100T.a4z 147875405265-5 +11       # the first giant and its neighbours
./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 29 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)

Without downloading 16 GB

Give the viewer the file's address instead of a file name. It fetches the header, the index entry and the one compressed chunk a query needs, a few hundred kilobytes in all, using curl and HTTP range requests:

./A400000_view https://this-site/files/A400000_100T.a4z 1e13 +20

The viewer needs curl (standard on macOS, Linux and Windows 10+) and a server that supports range requests, as nearly all static web servers do.

Commands

commandprints
info (default)number of terms, sum, hash, largest term, distinct heights, records
Na(N)
A Ba(A), …, a(B); B may be +K, meaning K terms from A
sum Na(1) + … + a(N), that is A397740(N)
recordsevery record height and where it stands (A399949, A399950)
first Hthe index of the first building of height H (A399763)
heightsevery height that occurs, with its first index and number of occurrences
verify [A B] [-j JOBS]decompress the chunks holding a(A..B) (default: all) and check them against the index; JOBS processes in parallel (each needs about 1 GB; the whole file takes about 40 CPU-hours)

Output formats: -f b b-file lines n a(n) (default), -f c a comma-separated list, -f v the values only. -o FILE writes to a file instead of the screen. Numbers can be written as 123, 1e13, 2^40, 1e13+5 or 2^40-1.

Each chunk touched costs up to about a second and about 1 GB of memory, the compression window. For long ranges the printing is the slow part: a b-file is about 15 bytes per term.

How the file is organized

The file holds 46,567 chunks of 231 consecutive terms each; the last holds 276,447,232. Each chunk stores one byte per term, with escape codes for the rare terms of 255 storeys or more, and is compressed as a single zstd frame. Before the chunks come:

The byte-level 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 recur exactly.

How the terms were checked

The hash: h = 0xcbf29ce484222325, then h = (h XOR a(n)) · 0x100000001b3 mod 264 for n = 1, 2, …. Over all 1014 terms it is 6a01a7624f4fc959, and the sum is 293,509,519,875,334.

The first 1014 terms in numbers

314,463the tallest building, a(22,433,065,737,435)
29records; none after n = 2.24·1013
2,342different heights; every height from 0 to 656 occurs, 657 does not
2.935095average height, S(n)/n at n = 1014

B-files

Plain-text b-files in the OEIS format (n a(n) per line), computed from the first 1014 terms (or, for the cross-referenced sequences, from the first 106):

sequencetermsfile
A400000100,000b400000.txt n = 1..100000 (part of a computation of the first 10^14 terms)
A399763657b399763.txt index of first building of height n in A400000, n = 0..656
A3974932,342b397493.txt distinct values of A400000 in order of appearance (first 100000000000000 terms)
A4001212,342b400121.txt indices of new terms in A400000 (first 100000000000000 terms)
A399965657b399965.txt inverse of A397493, n = 0..656 (first 100000000000000 terms)
A39994929b399949.txt record heights in A400000 (first 10^14 terms)
A39995029b399950.txt indices of the records of A400000 (first 10^14 terms)
A397740100,000b397740.txt partial sums of A400000, n = 1..N (computed from the stored terms, checked)
A397809100,000b397809.txt least building visible from A400000(n), a(1) = 0
A397831100,000b397831.txt indices of 1s in A400000
A399194100,000b399194.txt least h such that a building of height h at position n sees all earlier buildings
A399977100,000b399977.txt number of heights h with v_n(h) = h (candidates when computing A400000(n))
A400110100,000b400110.txt n - 1 - A400000(n)
A40011110,000b400111.txt T(n,k) = buildings visible from height k at position n, 0 <= k <= A399194(n)
A400133100,000b400133.txt (A400184(n)-1)/2
A400134100,000b400134.txt row n lists the indices of the buildings visible from A400000(n), n >= 2
A400183100,000b400183.txt even terms of A397831, divided by 2
A400184100,000b400184.txt odd numbers missing from A397831
A400708100,001b400708.txt consecutive buildings (A400000 raised by 1) visible from a pole of height n at 0
A40070925b400709.txt RUNS transform of A400708 (run lengths), complete runs within A400708(0..100000)