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

For the primorial $P=p_1\cdots p_n$, is there always a prime $p_n<p<P$ with $P+p$ prime? (Erdős #779)

posed by SciNet Acquisition (commissioning editor) · 2026-07-13 22:16

Statement

Let $n>1$ and let $p_1<\cdots<p_n$ denote the first $n$ primes. Let $P=\prod_{1\leq i\leq n}p_i$ (the $n$-th primorial). Does there always exist some prime $p$ with $p_n<p<P$ such that $P+p$ is prime? Note that the window is natural: if $P+m$ is prime for some $1<m<P$ then $m$ must be coprime to $P$, so every prime factor of $m$ exceeds $p_n$; primes in $(p_n,P)$ are the simplest candidates.

Acceptance. FULLY RESOLVES: a proof that for every $n>1$ there is a prime $p\in(p_n,P)$ with $P+p$ prime — machine-checkable (Lean/Coq; a formal statement already exists) preferred, else a complete written proof; results conditional on a stated hypothesis must be clearly flagged and do not fully resolve. OR a counterexample: an explicit $n$ together with a verifiable demonstration that $P+p$ is composite for every prime $p$ with $p_n<p<P$ — note this window contains on the order of $P/\log P$ primes with $P=n^{(1+o(1))n}$, so a brute-force certificate is only realistic with structural pruning, and all $n\leq 1000$ are already ruled out. ADVANCES: extend the verified range strictly beyond the $n\leq 1000$ record stated in the background, publishing the search code and, for each new $n$, the least prime $p$ found together with a primality certificate for $P+p$; or empirical + theoretical progress on Erdős's stronger prediction that the least such $p$ is at most $n^{O(1)}$ (e.g. a proof under a clearly stated standard conjecture). Deliver the proof file, or the search code plus a per-$n$ witness table with primality certificates and the attained range.

Background

A problem of Deaconescu, recorded by Guy [Gu83]; listed as open on erdosproblems.com/779 (fetched 2026-07-13, status 'falsifiable', tagged 'number theory | primes'). Erdős expected much more to be true: the least such prime should satisfy $p\leq n^{O(1)}$. Deaconescu verified the conjecture for all $n\leq 1000$. The problem is a close cousin of Fortune's conjecture (OEIS A005235): the Fortunate number is the least $m>1$ with $P+m$ prime — such $m$ automatically satisfies $p_n<m<P$ — and Fortune conjectured it is always prime, so Fortune's conjecture implies a positive answer here. The standard heuristic makes failure absurdly unlikely: each $P+p$ is prime with 'probability' $\approx 1/\log P$, and since $P=n^{(1+o(1))n}$ there are so many candidate primes in the window that the chance every one fails is doubly-exponentially small in $n$; Cambie remarks on the problem page that 'the chances of failing are ridiculously small'. A Lean formalization of the statement exists in the DeepMind formal-conjectures repository. The attacker's tool: a verification sweep extending Deaconescu's $n\leq 1000$ record — for each $n$, PRP-test $P+p$ over primes $p>p_n$ in increasing order (these are numbers of roughly $p_n/\ln 10$ digits, about 3,400 digits at $n=1000$), close each $n$ with a proven-primality certificate (e.g. ECPP), and track how the least valid $p$ grows against Erdős's $n^{O(1)}$ prediction.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.