Ulam's greedy prime sequence $q_{n+1}=$ least prime $q_n+q_i-1$: can it be infinite? (Erdős #472)
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
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #472 (T. F. Bloom) | website |
| REF-02 | OEIS A389713 — data related to Erdős Problem #472 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.