The program is a prime number. Source bytes are read as one big integer N; the encoded program is the N'th prime. Decoding means finding a given prime's index — which is, quite literally, an open problem in computational number theory.
Finding the index of a prime P — equivalently, computing π(P), the count of primes ≤ P — has no known algorithm running in time polynomial in the number of digits of P. Every known method (Legendre → Meissel → Lehmer → Lagarias–Miller–Odlyzko → Deléglise–Rivat → Gourdon) is sub-linear in P itself but still exponential in P's bit-length, and whether a genuinely polynomial-time algorithm exists is unresolved. This isn't a designed obstacle — it's the exact question analytic number theorists have been chipping at since 1870, with a public scoreboard: Meissel got π(10⁸) by hand; the current record, set by Baugh & Walisch in 2022, is π(10²⁹). Every time that record moves, the set of decodable PrimeIndex programs grows a little.
| source length | N (integer) | N'th prime ≈ | index-finding cost |
|---|---|---|---|
| 1 byte | ≤ 255 | ~1,600 | instant |
| 4 bytes | ~4.3×10⁹ | ~9.5×10¹⁰ | seconds |
| 8 bytes | ~1.8×10¹⁹ | ~8×10²⁰ | days, ordinary hardware |
| 12 bytes | ~7.9×10²⁸ | ~5.3×10³⁰ | past the current world record |
Source is read as tinylisp, its UTF‑8 bytes concatenated into one big integer N, and the output program is the N'th prime — found live below via a real Meissel‑style π(x) evaluation (φ(x,a) digit recursion with a 7‑prime wheel base case, memoized, plus the Meissel P2 correction) driving a binary search. Validated against a brute‑force sieve and the published π(10⁹)=50,847,534 / π(10¹⁰)=455,052,511 reference values — no lookup tables, no shortcuts.
Paste a prime P. A PrimeIndex program is, by definition, a value the encoder could have produced — and the encoder only ever outputs primes. So the decoder first runs a cheap Miller–Rabin primality check (deterministic for P below ~3.3×10²⁴, probabilistic with 40 rounds above that) and rejects anything composite outright, before spending any effort on the expensive part. Verifying validity is easy; only computing the index is hard. If P passes, its index is computed via the same Meissel‑style π(P) evaluation (a single evaluation, no binary search, which is why decoding is cheaper than encoding for the same magnitude), the byte stream is reconstituted from that index, and it's handed to the tinylisp evaluator.