Short Recurrences and Straight-Line Programs for Primes
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.
Related
- Straight-line programs for the solutions of Pell's equation
- Solving Classes of Linear Programs with Strongly Polynomial Straight Line Complexity in Strongly Polynomial Time
- A Sharp Bound of Crossing Limit Cycle for Planar piecewise linear Systems with a Straight Switching Line
- Realizing graph automorphisms as geometric symmetries of straight line drawings
- A class of low-rank short recurrences for nonsymmetric linear matrix equations
BibTeX
@misc{shunia2026short,
title = {{Short Recurrences and Straight-Line Programs for Primes}},
author = {Joseph M. Shunia and Mihai Prunescu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13365},
eprint = {2610.13365},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13365},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Short Recurrences and Straight-Line Programs for Primes
AU - Joseph M. Shunia
AU - Mihai Prunescu
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13365
UR - https://arxiv.org/abs/2610.13365
AB - 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.
ER -