Erdoes #779 - working report - Erdős Problem a Day

Erdős problem #779 — wave 6l

Access date: 2026-07-27 UTC

Outcome

The problem is not solved here. I obtained:

an elementary exact decomposition of the problem into a Cramér-scale

prime-gap term and a residual prescribed-gap prime-pair term;

a network-free verifier which reconstructs the primorials and uses PARI/GP

APRCL to certify explicit witnesses for every $2\leq n\leq100$;

an exhaustive check of the short-interval bijection for $2\leq n\leq15$;
a separately labelled BPSW (probable-prime, not proof) witness check at

$n=3001$, just beyond the first 3000 cases reported in the strongest primary source I found; and

measured costs explaining why extending the current table, and especially

turning the large probable primes into certified primes, is not a few-CPU-minute task.

Claim labels used below:

[A] elementary-rigorous;
[B] rigorous modulo the explicitly named theorem;
[C] plausible/structural-unverified;
[D] computational-only.

No claim labelled [C] or [D] is used as a theorem.

Step 0: authoritative live-page gate

I fetched the live page and its discussion thread through the Bright Data browser route (not direct curl):

<https://www.erdosproblems.com/779>
<https://www.erdosproblems.com/forum/discuss/779>

Verbatim live statement

Let $n> 1$ and $p_1<\cdots<p_n$ denote the first $n$ primes. Let $P=\prod_{1\leq i\leq n}p_i$. Does there always exist some prime $p$ with $p_n<p<P$ such that $P+p$ is prime?

Live status and page-supplied information

The badge is FALSIFIABLE (this is a type of open status, not “falsified”). The page explicitly says that its open status is the current belief of the site owner. It lists:

0 claimed proofs;
Interested in collaborating: None;
Currently working on this problem: None;
I am working on formalising the results: None.

Thus the mandatory skip condition did not fire.

The page calls this a problem of Deaconescu, says Erdős expected the least such $p$ to satisfy $p\leq n^{O(1)}$, and says Deaconescu verified the conjecture for $n\leq1000$. It also gives a random-prime heuristic and links OEIS A005235.

Clicking the page's bibliography entry gives:

[Gu83] R. Guy, A Miscellany of Erdős Problems. Amer. Math. Month. (1983), 118–120.

The bibliographic record exists as American Mathematical Monthly 90(2), 118–120, DOI 10.1080/00029890.1983.11971168. The publisher did not expose the full text in this environment, so I verified the metadata but do not claim an independent full-text check of Guy's wording.

All four live comments

The discussion thread contained the following substantive content:

Giorgos Kalogeropoulos, 2025-10-31: suggested the related sequence

A005235; the site notes that it was subsequently added.

Dogmachine, 2025-09-22: observed that the conjecture would make every

primorial a difference of two primes, that even this weaker unrestricted claim has no known proof, and that the left-hand inequality can be omitted.

StijnC, 2025-09-22: compared the unrestricted difference problem with the

twin-prime problem and Schinzel's hypothesis H, while noting the difficulty.

Dogmachine, 2025-08-09: compared the question with Fortune's conjecture

and called it similarly intractable with current methods.

These are comments, not verified results. Section 3 below proves the left-hand-inequality observation and spells out the uniformity missing from the Schinzel-H observation.

1. Literature search

I searched the exact statement, “Deaconescu” plus primorial/prime, A005235, Fortune's conjecture, the Guy citation, and recent work through July 2026. I found no primary source claiming a proof or counterexample to #779. This is a report of the search, not a proof that no such source exists.

1.1 Directly relevant sources

**Solomon W. Golomb, “The Evidence for Fortune's Conjecture,”

Mathematics Magazine 54(4) (1981), 209–210.** DOI 10.1080/0025570X.1981.11976928. The journal metadata and title are verified. This is the classical source for the stronger assertion about the least offset.

**Antonín Čejchan, Michal Křížek, and Lawrence Somer, “On Remarkable

Properties of Primes Near Factorials and Primorials,” Journal of Integer Sequences 25 (2022), Article 22.1.4. Primary HTML and PDF. Their Theorem 17 states that, for consecutive primes $q<r$, if a prime $Q$ satisfies \[ q\# +1<Q<q\#+r^2, \] then $Q-q\#$ is prime. [A, as reproved below] Their Remark 21 reports that Fortune's conjecture has been checked for the first 3000 primes, via A005235. [D]**

**Cyril Banderier, “Fortunate and unfortunate primes: nearest primes from

a prime factorial.” Author's computation page. The currently served page says $n<1300$, explicitly warns that its large “prime” decisions used probable-prime algorithms, and records a later independent Mathematica check through $n=2000$. [D]**

**Hayat Rezgui, “New explorations and remarkable inequalities related to

Fortune's conjecture and fortunate numbers,” General Letters in Mathematics 13(3) (2023), 58–76. DOI 10.31559/glm2023.13.3.1. The abstract and paper describe a sufficient special case and numerical inequalities for the first 3000 entries; they do not supply the missing uniform prime-gap or prime-pair theorem. [D for the 3000-case data]**

**Michael M. Ross, “Sifted Symmetry and Sieve Structures of Primorial

Goldbach Complements,” Zenodo record 21194754, version dated 2026-07-23.** Record. This is a very recent, non-peer-reviewed preprint mainly about the lower-side (Goldbach/lesser-Fortunate) problem. Its Remark 5.6 accurately restates the upper-side $p_{n+1}^2$ criterion and the 3000-case report; it does not claim to solve the upper-side question here.

OEIS A005235.

Entry and current 4600-row b-file. This is an auxiliary live database, not a proof source. The entry text still says “first 2000,” the 2022 JIS paper says 3000, and the current b-file contains 4600 candidate offsets. No primality certificates for the enormous shifted primorials accompany that b-file. [D]

1.2 General prime-gap benchmark

R. C. Baker, G. Harman, and J. Pintz, “The Difference Between Consecutive Primes, II,” Proceedings of the London Mathematical Society 83 (2001), 532–562, DOI 10.1112/plms/83.3.532, prove that every sufficiently large interval $[x,x+x^{0.525}]$ contains a prime. [B: Baker–Harman–Pintz] This is vastly longer than the $O((\log x)^2)$ interval needed by the short-gap route below.

2. Definitions and relation to A005235

Write

P=P_n=\prod_{i=1}^n p_i,\qquad r=p_{n+1}.

Define the least nontrivial upper offset

F_n=\min\{m>1:P+m\ \hbox{is prime}\}.

This is A005235's Fortunate number. Fortune's conjecture says $F_n$ is always prime. Problem #779 is weaker in one sense—it permits any prime offset, not necessarily the least one—but it also explicitly requires the offset to be below $P$.

An A005235 value is therefore a #779 witness whenever it is actually prime, $P+F_n$ is actually prime, and $F_n<P$. [A]

3. Elementary exact reduction

Lemma 1: the lower inequality is automatic

If $p$ and $P+p$ are prime, then $p>p_n$. [A]

Proof. If $p\leq p_n$, then $p\mid P$, hence $p\mid(P+p)$. But $P+p>p$, so $P+p$ would be composite. $\square$

Thus the “left-most inequality can be omitted” comment is correct.

Lemma 2: rough offsets and the square threshold

If $m>1$ and $P+m$ is prime, then every prime divisor of $m$ is at least $r=p_{n+1}$. Consequently,

1<m<r^2\quad\Longrightarrow\quad m\ {\rm is\ prime}. \tag{1}

[A]

Proof. If a prime $\ell\leq p_n$ divided $m$, then it would divide both $P$ and $P+m$. Since $P+m>P\geq\ell$, this contradicts the primality of $P+m$. Thus $m$ is $p_n$-rough. If it were composite, its least prime factor and its cofactor would both be at least $r$, giving $m\geq r^2$. $\square$

Lemma 3: the square window lies inside the required range

For every $n\geq4$,

p_{n+1}^2<P_n. \tag{2}

[A]

Proof. At $n=4$, $11^2=121<210=P_4$. If $P_n>p_{n+1}^2$, let $s=p_{n+2}$. Bertrand's postulate gives $s<2p_{n+1}$, while

P_{n+1}=P_n p_{n+1}>p_{n+1}^3>4p_{n+1}^2>s^2.

This proves the induction. $\square$

Proposition 4: exact Cramér-window bijection

For an integer $H$ with $2<H\leq r^2$, subtraction of $P$ is a bijection

\begin{split} \{Q:\;&P+1<Q<P+H,\ Q\ {\rm prime}\}\\ &\longleftrightarrow \{p:\;2\leq p<H,\ p\ {\rm prime},\ P+p\ {\rm prime}\}. \end{split} \tag{3}

In particular,

\#\{p<H:p,\ P+p\ {\rm prime}\} =\pi(P+H-1)-\pi(P+1). \tag{4}

[A]

Proof. Given a prime $Q$ on the left, set $m=Q-P$. Then $1<m<H\leq r^2$, so Lemma 2 makes $m$ prime. The reverse map is $p\mapsto P+p$. The two maps are inverse. $\square$

The verifier exhaustively checks (3), with $H=r^2$, for every $2\leq n\leq15$. [D]

Corollary 5: exact split of #779

For $n\geq4$, let

T_n=\#\{p:\ r^2\leq p<P,\ p\ {\rm prime},\ P+p\ {\rm prime}\}.

Then the total number $W_n$ of #779 witnesses is exactly

\boxed{ W_n=\pi(P+r^2-1)-\pi(P+1)+T_n. } \tag{5}

Problem #779 is equivalent to $W_n>0$ for every $n\geq4$, together with the direct cases $n=2,3$. [A]

The direct cases are

n=2:\ P=6,\ p=5,\ P+p=11;\qquad n=3:\ P=30,\ p=7,\ P+p=37.

[A]

Formula (5) isolates two genuinely different possible routes:

Cramér-scale route. Prove that $(P+1,P+r^2)$ contains a prime.

By (3), its offset is automatically prime and, by (2), below $P$.

Tail prime-pair route. If that short interval is empty, prove

$T_n>0$, i.e. find a prime $p\in[r^2,P)$ for which $p+P$ is prime.

Neither implication is lost: (5) is an equality, not a heuristic.

4. The exact missing analytic statements

4.1 Short-gap route

A sufficient lemma is the pointwise bound

\min\{m>1:P_n+m\ {\rm prime}\}<p_{n+1}^2 \quad\text{for every sufficiently large }n. \tag{6}

Finite remaining $n$ could then be checked. [A]

Since

\log P_n=\vartheta(p_n)\sim p_n,\qquad p_{n+1}^2\sim(\log P_n)^2,

(6) is a Cramér-scale prime-gap assertion at the sparse points $P_n$. [B: prime number theorem]

Baker–Harman–Pintz only supplies an interval of length $P_n^{0.525}$, which is exponentially larger than $p_{n+1}^2=n^{2+o(1)}$. [B: Baker–Harman–Pintz and PNT] It therefore cannot trigger Lemma 2.

4.2 Tail route and the parity barrier

The tail asks for a lower bound on

R(P;P)=\sum_{\substack{p<P\\p\ {\rm prime}}} \mathbf 1_{\mathbb P}(p+P) \tag{7}

for the prescribed, growing even shift $P=P_n$. A uniform Hardy–Littlewood prime-pair asymptotic valid pointwise when the shift and search length are both $P$ would give

R(P;P)\sim 2C_2\!\!\prod_{\substack{\ell\mid P\\\ell>2}} \frac{\ell-1}{\ell-2} \int_2^P\frac{dt}{\log t\,\log(t+P)}. \tag{8}

For a primorial,

2C_2\prod_{3\leq\ell\leq p_n}\frac{\ell-1}{\ell-2} \sim e^\gamma\log p_n,

so (8) predicts

R(P;P)\sim e^\gamma\log p_n\,\frac{P}{(\log P)^2}\longrightarrow\infty. \tag{9}

[C: Hardy–Littlewood heuristic; not a theorem]

The exact missing lemma on this route is a positive pointwise lower bound for (7), uniformly at $h=x=P_n$. Ordinary two-dimensional sieve gives upper bounds but not a positive lower bound for two simultaneous primes: this is the parity obstruction.

Qualitative Schinzel H applied after fixing a single $P$ predicts infinitely many primes $p,p+P$, but it gives no uniform guarantee that one occurs before $p=P$. Thus the qualitative fixed-polynomial statement does not, by itself, prove the upper bound required in #779. [A: logical quantifier observation]

Likewise, bounded-gap theorems locate some recurring bounded gap; they do not force the specified growing gap $P_n$. [A]

5. Reproducible computation

The standalone verifier is:

runs/erdos779_wave6l_verify.py

It uses only the Python standard library and the installed PARI/GP executable. It does not download or trust the OEIS table at runtime: candidate offsets are embedded, the first 4602 primes are rebuilt with an Eratosthenes sieve, and every asserted arithmetic relation is recomputed.

Run:

python runs/erdos779_wave6l_verify.py

PARI/GP version in the successful run: 2.15.4.

5.1 Exact finite block $2\leq n\leq100$

For all 99 values $2\leq n\leq100$, the verifier checks:

the offset $p$ is prime;
$p_n<p<P_n$;
isprime(P_n+p,2) == 1.

PARI documents flag 2 as the deterministic APRCL primality test, not BPSW. No external certificate file is emitted, so I conservatively classify this finite block as [D] computational-only, albeit with a proof-grade primality algorithm rather than a probable-prime test.

Selected rows:

$n$	$p_n$	witness $p$	digits of $P_n$	result
2	3	5	1	APRCL prime $P+p=11$
3	5	7	2	APRCL prime $P+p=37$
4	7	13	3	APRCL prime $P+p=223$
5	11	23	4	APRCL prime $P+p=2333$
10	29	61	10	APRCL prime
25	97	103	37	APRCL prime
50	229	293	92	APRCL prime
75	379	409	154	APRCL prime
100	541	641	220	APRCL prime

The complete 99-row transcript is deterministically represented by

small_table_sha256 =
a2bfc46bfeea17cb9f9b674167f506261dcd019fe8244250db1f2746e87a164d

The largest offset in this block is $1381$, at $n=70$, and all full integer rows are generated by the verifier. [D]

5.2 Exhaustive short-window identity

For each $2\leq n\leq15$, the script enumerates both sides of (3) for $H=p_{n+1}^2$. All tested integers are below $2^{64}$; it uses the standard deterministic seven-base Miller–Rabin theorem for this range. The two sets agree in every case. [D, rigorous modulo the deterministic 64-bit Miller–Rabin base theorem]

The counts are

[(2, 6), (3, 10), (4, 19), (5, 23), (6, 29), (7, 25),
 (8, 38), (9, 42), (10, 35), (11, 56), (12, 54),
 (13, 45), (14, 60), (15, 67)]

and the enumerated-set transcript hash is

251e0911a815011d7bbd920ff11211e975bdbf5515c5675f07990a151f1378ee

This computation tests the implementation; Proposition 4 itself was proved for all $n$ independently of the computation.

5.3 A deliberately non-rigorous checkpoint at $n=3001$

The current A005235 b-file gives the candidate offset $p=33211$. The verifier independently recomputes:

n             = 3001
p_n           = 27457
digits(P_n)   = 11833
p             = 33211
isprime(p,2)  = 1
p_n < p < P_n
ispseudoprime(P_n+p) = 1   # PARI BPSW
P_n mod 1000000007 = 149874951

The exact integer $P_n+p$, represented without printing all 11833 digits, has

sha256(decimal(P_n+p)) =
79f309b87fca624b205ea1090716f8ccd3502fc61e4e95e384c225f04b31e777
first 32 digits = 51602038179433115646345337470223
last  32 digits = 18921544259369476798319951327881

This is [D] computational-only. BPSW passing does not prove that $P_{3001}+33211$ is prime, and I do not call it prime in this report. Nor did I re-establish that 33211 is the least offset; minimality is irrelevant for its use as a #779 candidate.

The final complete verifier run took 49.66 wall-seconds. It also reproduced the $n=1001$ BPSW checkpoint from Section 6.1 and the $n=4601$ size and heuristic inputs from Section 6.2.

5.4 Core verification code

The full executable code is in the standalone file. Its decisive PARI calls are:

# Exact finite block:
for n in range(2, 101):
    assert p_n < witness[n] < P_n
    assert isprime(witness[n], 2)       # APRCL
    assert isprime(P_n + witness[n], 2) # APRCL

# Large checkpoint, intentionally not promoted to a proof:
assert ispseudoprime(P_1001 + 8831)     # BPSW only
assert ispseudoprime(P_3001 + 33211)    # BPSW only

The actual file constructs the primes and primorials from scratch, invokes GP in one checked subprocess, parses all 99 certificates, performs the independent 64-bit bijection enumeration, and hashes the transcripts.

6. Bounded failed computations and realistic cost

6.1 Proof attempt at $n=1001$

For the candidate $p=8831$, $P_{1001}+8831$ has 3397 decimal digits. A BPSW check took about one second, but this is not a proof. PARI APRCL required repeatedly expanding its stack; the final bounded attempt used 93.17 CPU-seconds and reached about 4.8 GB resident memory before I interrupted it at an 8 GB configured stack. Pocklington–Lehmer mode also failed to finish within two CPU-minutes. No exact primality claim is made.

6.2 Attempt to extend the b-file to $n=4601$

Here

p_4601        = 44203
digits(P_4601)= 19113

PARI nextprime(P+2) (which searches for a BPSW pseudoprime, not a proven prime) was stopped at the hard cap of 239.94 CPU-seconds without returning a candidate. Therefore no $n=4601$ value is claimed.

A separate timing probe of the first prime offset $p=44207$ found $P_{4601}+44207$ BPSW-composite in 22.62 seconds (PARI reported 22,620 ms). This can be repeated with --skip-large --benchmark-4601. [D]

Under the prime-pair heuristic, a prime offset has conditional success probability about

\frac{e^\gamma\log p_{4601}}{\log P_{4601}} =0.0004329\ldots,

or roughly 2310 expensive survivors per success. [C] At the measured 22.7 seconds per composite test, a straightforward serial extension is therefore approximately 15–30 core-hours, allowing for the slower successful BPSW test and search overhead. [C: cost estimate] At a representative \$0.05–\$0.15 per vCPU-hour, that is roughly \$1–\$5; parallel execution would reduce wall time but not core-hours. This is why I did not run it on the present few-minute budget.

A proof-grade ECPP certificate for an 11,833- or 19,113-digit general-form candidate is a much larger job than the BPSW search. Extrapolating published general-purpose ECPP/APRCL timings gives at least hundreds, plausibly thousands, of core-hours, with substantial input-to-input variance. [C: engineering estimate, not a theorem]

7. What has and has not been established

The lower inequality $p_n<p$ is redundant. [A]
Every prime value $P+m$ with $1<m<p_{n+1}^2$ automatically has prime

offset $m$. [A]

Equation (5) is an exact reduction: the remaining alternatives are a

Cramér-scale gap at the primorial or a positive prescribed-gap prime-pair count in the tail. [A]

Explicit #779 witnesses for $2\leq n\leq100$ were independently

rechecked with APRCL. [D]

The literature reports computational verification of the stronger

Fortune conjecture through $n=3000$, and the live OEIS b-file currently has 4600 candidate rows. [D]

The $n=3001$ shifted primorial passed BPSW in this run, but has not been

proved prime here. [D]

Neither the required uniform Cramér-scale prime-gap lemma nor the required

pointwise lower-bound prime-pair lemma is presently available. Hence there is no uniformity/finiteness step closing #779.

PARTIAL: proved the exact Cramér-window/tail decomposition, APRCL-reverified witnesses for 2<=n<=100, and BPSW-checked (not proved) the n=3001 candidate; the uniform prime-gap/prime-pair step remains open.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger

Erdős problem #779 — wave 6l

Outcome

Step 0: authoritative live-page gate

Verbatim live statement

Live status and page-supplied information

All four live comments

1. Literature search

1.1 Directly relevant sources

1.2 General prime-gap benchmark

2. Definitions and relation to A005235

3. Elementary exact reduction

Lemma 1: the lower inequality is automatic

Lemma 2: rough offsets and the square threshold

Lemma 3: the square window lies inside the required range

Proposition 4: exact Cramér-window bijection

Corollary 5: exact split of #779

4. The exact missing analytic statements

4.1 Short-gap route

4.2 Tail route and the parity barrier

5. Reproducible computation

5.1 Exact finite block \(2\leq n\leq100\)

5.2 Exhaustive short-window identity

5.3 A deliberately non-rigorous checkpoint at \(n=3001\)

5.4 Core verification code

6. Bounded failed computations and realistic cost

6.1 Proof attempt at \(n=1001\)

6.2 Attempt to extend the b-file to \(n=4601\)

7. What has and has not been established

\(n\)	\(p_n\)	witness \(p\)	digits of \(P_n\)	result
2	3	5	1	APRCL prime \(P+p=11\)
3	5	7	2	APRCL prime \(P+p=37\)
4	7	13	3	APRCL prime \(P+p=223\)
5	11	23	4	APRCL prime \(P+p=2333\)
10	29	61	10	APRCL prime
25	97	103	37	APRCL prime
50	229	293	92	APRCL prime
75	379	409	154	APRCL prime
100	541	641	220	APRCL prime