# two-base-gasket

- Computes `C(N) = card(A cap B cap [0, N)^2)` exactly, where `A` is the base-2 gasket `{(x, y) : x AND y = 0}` and `B` is the base-3 gasket, the pairs whose base-3 digit pairs all lie in `{(0,0), (0,1), (1,0)}`.
- Exact integer arithmetic throughout; no sampling, no fit.
- The fast count walks the base-3 exponents from the top down, choosing for each whether `3^i` joins `x`, joins `y` or neither, and prunes a branch when the high halves of `x` and `y` cannot be made disjoint: with `B_k` the bit length of `3^k` and `k` exponents still unread, the remaining addition to each coordinate is below `3^k`, so each final high part `x >> B_k` is its current value or one more, and a branch dies when all four combinations of the two high parts share a bit.
- Also prints the naive planar budget `dim A + dim B - 2` and the axis lower bound `2^(m+1) - 1`, with the bound truncated down and the budget rounded up.
- The recurrence test is exact over `Q`: Bareiss integer Hankel determinants, and one rational Gauss-Jordan per order on every equation the terms supply, so a reported absence is a proof that no such recurrence fits the terms given, and nothing else.

## VERBS

- `budget` prints `dim A = log_2 3`, `dim B = log_3 3`, the budget `dim A + dim B - 2` rounded up, the axis exponent `log_3 2` truncated down, and the excess. Runtime under `0.05` s.
- `control M` recomputes `C(3^m)` for `m = 0..M` twice: once by the pruned walk and once by testing every pair `(x, y)` in `[0, 3^m)^2` against both digit rules with one shared routine, and prints whether the two agree and whether the axis bound holds. Runtime `0.2` s at `M = 6`.
- `terms LO HI` prints `C(3^m)`, the axis bound `2^(m+1) - 1`, the ratio to the level below and `log_3 C(3^m) / m`, asserting the axis bound at every level. Runtime `3` min `13` s for `LO HI` equal to `0 24` on one core, the cost per level rising by a factor near `2.1`; `m = 25` costs about `3.5` min more and is not run.
- `hankel HI [RMAX]` recomputes `C(3^m)` for `m = 0..HI` and prints them, prints the Hankel determinants `det H_k` of the matrix with entries `a[i+j]` for `k = 1..RMAX+1`, and for each order `r = 1..RMAX` solves the system `a(n) = c_1 a(n-1) + ... + c_r a(n-r)` over every `n` with `r <= n <= HI`, printing the number of equations, the equations spare after the `r` unknowns, and either `none` for an inconsistent system or the coefficients. A consistent order also gets its characteristic polynomial and the modulus of its dominant root from `gp -q`. `RMAX` defaults to `12`, which is the largest order `HI = 24` leaves a spare equation for, order `r` wanting `2r+1` terms and so order `13` wanting `HI = 26`. Runtime `3` min `15` s at `HI = 24`, the census being the whole cost and the algebra under `0.01` s.
- `selftest` runs the algebra of `hankel` against answers known in advance: `bareiss` on five determinants computed by hand, reading `3`, `-2`, `-6`, `0` and `4`, the third needing a pivot swap and the fourth singular; the Fibonacci numbers, first fitted at order `2` with characteristic polynomial `x^2 - x - 1`; `2^n + 3^n + 1`, first fitted at order `3` with dominant root `3.0000000` from `gp -q`; and `n^3 + 2^n`, fitted at no order below `5` and at `5` with `(x - 1)^4 (x - 2)`. Eleven checks, each printing its expected value beside what it got. A solver that answered `none` to everything would fail the three positive fits, and one that fitted anything would fail `n^3 + 2^n` below order `5`. Runtime `0.05` s.

## RUN

- From the repo root.

```
uv run python research/lab/py/two-base-gasket/census.py budget
uv run python research/lab/py/two-base-gasket/census.py control 6
uv run python research/lab/py/two-base-gasket/census.py terms 0 24
uv run python research/lab/py/two-base-gasket/census.py hankel 24 12
uv run python research/lab/py/two-base-gasket/census.py selftest
```

## WITNESSES

- `cobham.md:76` the budget `0.584963`
- `cobham.md:77` the twenty-five terms `C(3^m)` at `m = 0..24` and the control that rebuilds them to `m = 6`
- `cobham.md:78` the axis lower bound `C(3^m) >= 2^(m+1) - 1`
- `cobham.md:79` the excess `log_3 2 >= 0.630929` over `0.584963`
- `cobham.md:81` the falling readings `log_3 C(3^m) / m` at `m = 14..24`