# mixed-powers

- Computes, for a finite base set `D` of integers `>= 3` and a level `k >= 1`, whether every large integer is a sum of distinct terms of the multiset `M_k(D)` of powers `d^j`, `d` in `D`, `j >= k`, one copy per base: Erdos problem 124 at one level.
- The certificate is the surplus certificate of `research/notes/erdos.md`: the sums `P_n` of the `n` least terms are held as one bit array, each term folded in by one shift-or pass, and after each term `T = 1 + max{x <= S_n/2 : x not in P_n}` is read by a word scan down from `S_n/2`; when `T <= a_(n+1)` and the step `a_(m+1) <= S_m - 2T + 1` holds until the surplus `(sigma - 1) a_(m+1) >= C_k + 2T - 1` takes over, the level is complete and `F = T - 1` is the largest integer that is no sum. The step check runs over the terms up to `10^30` in exact integer arithmetic, `sigma` and `C_k` over the common denominator of the `d - 1`.
- The census enumerates the base sets in `[3, R]` minimal for `sigma > 1` and `gcd = 1`, every other such set containing one, and certifies each at `k = 1, 2, ...` until a cell passes the bit cap.
- The route verb reads, per minimal base set, the least `sum(M_1(D) below N)/N` over terms `N` in `[10^E, 10^30]`, truncated to six places, the quantity that bounds two-part partitions below `sigma = 2`.

## VERBS

- `census R K BITS THREADS`: every minimal base set in `[3, R]` at `k = 1..K` with a `2^BITS`-bit array per cell; prints `F`, the count of positive non-sums up to `F`, the index `n` and term `a_n` of the certificate, `S_n`, the term where the surplus takes over, and the depth histogram. Runtime `2.9` s at `census 10 5 32 4`, `8.7` s at `census 12 5 32 4`, on `4` threads, `512` MB per thread.
- `cell D K BITS`: one base set, comma separated, at one level. Runtime `1.0` s at `cell 3,4,5 4 34`, `1.3` s at `cell 3,6,9,10,12 2 34`, `2` GB.
- `control`: nine cells against a plain knapsack over every term up to `4 F`, same `F` and same count of non-sums, and a `gcd = 3` set that never certifies below `2^24`. Runtime `0.9` s.
- `set D K B`: the same base set read as a set of powers, ties counted once, by a plain knapsack to `B`; prints the largest non-sum below `B`. Runtime under `0.01` s at `set 3,5,6,9 1 20000`, which reads `649` against the multiset's `F = 22`.
- `windows D K E F`: over the terms `a_(n+1)` in `[10^E, 10^F]` of `M_K(D)`, the count of windows `a_(n+2) > S_n` and of pairs `m < n` of windows where the upper window `(S_m, a_(m+2))` meets the lower window `(S_n - a_(n+1), a_(n+2) - a_(n+1))`. Runtime under `0.01` s at `windows 3,4,5 1 6 30`: `27` of `123`, no pair.
- `graham T P Q BITS`: the set `floor(T (P/Q)^n)`, `n >= 1`, up to `2^BITS`, exact in integers; the count of windows and of windows holding a non-sum, and the largest non-sum up to `2^(BITS-1)`. Runtime under `0.1` s at `graham 2 5 3 26`: `31` windows, all holding a non-sum, largest `23559582`.
- `refute BITS`: the set `2 F_m - 1`, `m >= 2`, up to `2^BITS`, which refutes the surplus lemma L of the note: the least of `2 (S_n - a_(n+1)) - a_(n+1)`, the windows and those holding a non-sum, and the non-sums below `10^6`. Runtime under `0.1` s at `refute 27`: `36` windows, all holding a non-sum.
- `ternary N HI THREADS`: `g_3(n)` of Erdos problem 817 for `n = 1..N`, exhaustive: for each largest element in turn, a search from the top down over sets whose `3^n` ternary sums are distinct, one bit array of sums, pruned by `g_3(r)` of the run before and by `sum a_i^2 >= (9^n - 1)/8`. Runtime `5.9` s at `ternary 6 200 8`.
- `probe N TOP THREADS`: the same search at one largest element. Runtime `36` s at `probe 7 380 8`.
- `band LO HI W THREADS`: the least largest element in `[LO, HI]` of an admissible 7-set whose six largest elements lie within `W` of it, exhaustive inside that band. Runtime `2.8` s at `band 419 475 70 8`, which finds `{302, 409, 447, 459, 465, 466, 474}`, and `114` s at `band 419 473 100 8`, which finds none.
- `offsets LO HI`: the offset families `{0, 1, 3, 8, 22, 60}`, `{0, 2, 6, 9, 23, 61}`, `{0, 2, 5, 7, 21, 60}` below a largest element plus one free offset. Runtime `1.3` s.
- `route R E`: the least ratio per minimal base set in `[3, R]` over terms in `[10^E, 10^30]`. Runtime under `0.01` s.

## RUN

```
bash scripts/cargo.sh cargo run --release -p mixed-powers -- census 10 5 32 4
bash scripts/cargo.sh cargo run --release -p mixed-powers -- census 12 5 32 4
bash scripts/cargo.sh cargo run --release -p mixed-powers -- cell 3,4,5 4 34
bash scripts/cargo.sh cargo run --release -p mixed-powers -- cell 3,6,9,10,12 2 34
bash scripts/cargo.sh cargo run --release -p mixed-powers -- control
bash scripts/cargo.sh cargo run --release -p mixed-powers -- set 3,5,6,9 1 20000
bash scripts/cargo.sh cargo run --release -p mixed-powers -- route 10 12
bash scripts/cargo.sh cargo run --release -p mixed-powers -- windows 3,4,5 1 6 30
bash scripts/cargo.sh cargo run --release -p mixed-powers -- graham 2 5 3 26
bash scripts/cargo.sh cargo run --release -p mixed-powers -- refute 27
bash scripts/cargo.sh cargo run --release -p mixed-powers -- ternary 6 200 8
bash scripts/cargo.sh cargo run --release -p mixed-powers -- band 419 475 70 8
bash scripts/cargo.sh cargo run --release -p mixed-powers -- band 419 473 100 8
```

- `bash scripts/cargo.sh cargo test --release -p mixed-powers`, `7` tests, under `1` s after the build.

## READS

- `30` minimal base sets in `[3, 10]`, all certified at `k = 1, 2, 3`, `21` at `k = 4`, `5` at `k = 5`; `103` in `[3, 12]`, all at `k = 1, 2` with `{3, 6, 9, 10, 12}` at `k = 2` from the cell verb, `F = 1473914231`.
- `F({3, 4, 5}, k)` at `k = 1..4`: `79, 77613, 4330731, 1075364603`, with `11, 1128, 45704, 1785062` positive non-sums up to `F`; `F({3, 4, 6}, k)` at `k = 1..3`: `986, 242113, 58941162`.
- The one base set in `[3, 12]` with `sigma = 1` and `gcd = 1` is `{3, 4, 7}`, outside the certificate.
- Route ratios over `[10^12, 10^30]` for the `30` minimal base sets in `[3, 10]`: between `1.105953` and `1.537469`.

## WITNESSES

- `research/claims/erdos.md`, every row citing this study:
- `route 10 12`: the two-part obstruction at twelve digits.
- `census 10 5 32 4`: cofinite at `k = 1, 2, 3` for every base set in `[3, 10]`.
- `census 12 5 32 4` and `cell 3,6,9,10,12 2 34`: cofinite at `k = 1, 2` for every base set in `[3, 12]`.
- `census 10 5 32 4`, `cell 3,4,5 4 34` and `control`: the largest non-sums of `{3, 4, 5}` and `{3, 4, 6}` and the knapsack agreement.
- `census 10 5 32 4` and `cell 3,4,5 4 34`: the Conjecture row on `{3, 4, 5}` at every level.
- `cell 3,5,6,9 1 20` and `set 3,5,6,9 1 20000`: sets and multisets differ on tie cells.
- `graham 2 5 3 26`: the seed of the incompleteness of `floor(2 (5/3)^n)`.
- `windows`: the power multisets run no window chain.
- `census 10 5 32 4`, `cell 3,4,5 4 34` and `cell 3,4,5 5 34`: the certificate for `{3, 4, 5}` at `k = 5` passes `2^34` bits.
- `refute 27`: the Refuted row on the surplus lemma L.
- `ternary 6 200 8`: `g_3(n)` for Erdos problem 817 at `n = 1..6`.
- `band 419 475 70 8` and the crate test on the set: `g_3(7) <= 474`.
- `band 419 473 100 8`: no set beating `474` with its six largest elements within `100` of the top.
- The certificate, exactness, monotone, two-part, window and surplus-does-not-heal rows are proofs on `research/notes/erdos.md`.