PrimeIndex

PrimeIndex is an esoteric programming language by User:AndrewBayly in which the source code, read as one large integer N, is encoded as the N-th prime number. Decoding a PrimeIndex program means recovering N from a given prime — that is, computing how many primes precede it. This is not merely slow; it is, as far as anyone has proven, an open problem in computational number theory whether it can be done in time polynomial in the number of digits of the prime. PrimeIndex is the fifth member of an "asymmetry" family of languages by the same author, and may be considered the most mathematically elegant of the set: its entire mechanism is described by one sentence, with no arbitrary constants, no bitwise operations, and no auxiliary encoding key.

• PrimeScript — hard to execute (a prime is used as a multiplicative encoding key; decoding requires factoring)
• Square — hard to execute (decoding requires a permutation search to reassemble blocks)
• Trapdoor — hard to write (a valid program must satisfy a modular constraint)
• Hard — hard to write and execute (both directions require computing bits of π at factorial-indexed positions)
• PrimeIndex — hard to write and execute (both directions require locating a specific prime's ordinal position, an open problem)

PrimeIndex is a sister language to PrimeScript: PrimeScript uses a prime as an encoding key multiplied against the source, while PrimeIndex dispenses with the key entirely and makes a prime be the program.

External resources

• Reference implementation and interactive demo — a browser-based (HTML/JS) implementation featuring a real Meissel-style π(x) evaluator (φ(x,a) digit recursion with a wheel-sieve base case, memoization, and the Meissel P2 correction term), validated against brute-force sieving and the published π(10⁹), π(10¹⁰) and π(10¹¹) reference values; live encode/decode with real timing, an analytical time estimator calibrated to the implementation's own measured throughput for inputs beyond exact-precision range, and a Miller–Rabin validity check on decode.

See also

• Hard
• PrimeScript
• Square
• Trapdoor
• tinylisp