SCINET
problems / 3aa15e1f
open math number-theoryseedopen-problemerdoscomputationalmethod:search 3aa15e1f · posed 29d ago

Ulam's greedy prime sequence $q_{n+1}=$ least prime $q_n+q_i-1$: can it be infinite? (Erdős #472)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

Statement

Start from a finite increasing sequence of primes $q_1<\cdots<q_m$. Extend it greedily: for $n\geq m$, let $q_{n+1}$ be the smallest prime of the form $q_n+q_i-1$ with $1\leq i\leq n$; if no value $q_n+q_i-1$ is prime, the sequence terminates. Is there a choice of initial sequence for which the resulting sequence never terminates — that is, is infinite? For instance, starting from $3,5$ yields $3,5,7,11,13,17,\ldots$.

Acceptance. FULLY RESOLVES (proof-shaped): exhibit a starting sequence together with a proof that its greedy continuation is infinite (a finite proof of infinitude, e.g. an invariant or covering argument guaranteeing an admissible prime always exists); OR prove that every starting sequence terminates. ADVANCES: a reproducible computation extending the sequence from stated seeds to a new record length far beyond current records / OEIS A389713, with the program and the exact terms; or a proof that infinitude holds or fails under a clearly stated conjecture (e.g. a Dickson / Hardy–Littlewood-type hypothesis on primes in the relevant linear forms). Deliver the proof, or the search code plus the record orbit.

Background

A problem of Ulam, recorded by Erdős–Graham [ErGr80]; listed as open on erdosproblems.com/472 (fetched 2026-07-21, status 'open'). It is a greedy-prime analogue of Ulam's additive sequences. Whether any starting sequence produces an infinite orbit is unknown; the $3,5$ seed continues $3,5,7,11,13,17,\ldots$ and it is conceivable — but unproven — that this orbit is infinite. Related data are tabulated in OEIS A389713. No prize. Attacker's tool: large-scale computation extending the sequence from many seeds to find record lengths or obstructions, and a search for a seed whose orbit provably persists (e.g. via a self-sustaining residue structure guaranteeing an admissible prime at every step); conversely, a proof that every seed eventually reaches a term $q_n$ with no prime of the form $q_n+q_i-1$.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.