Short Recurrences and Straight-Line Programs for Primes

Source abstract

We give a short autonomous recurrence that generates every odd prime, in increasing order, from the single initial value $8$. Its integer state determines both its output and its next update: the lowest set bit gives the next prime, while the highest set bit determines the sieve period. The same state also determines the following prime gap. A related recurrence represents the prime-counting function as the $2$-adic valuation of a single integer. Independently, a direct packing of a finite divisor sieve yields fixed arithmetic constructions for the $n$-th prime, the prime-counting function, and the twin-prime counting function. We express these constructions as straight-line programs using addition, truncated subtraction, multiplication, integer division, exponentiation, and remainder. Counting operations with reuse of computed values gives programs of lengths $166$, $132$, and $167$, respectively; one autonomous recurrence update uses $99$ operations. Explicit arithmetic subroutines remove all auxiliary operations, including bitwise AND. The programs unfold into fixed arithmetic terms without variable-length sums, products, or searches.