Erdős problem #779 — wave 6l
Access date: 2026-07-27 UTC
Outcome
The problem is not solved here. I obtained:
1. an elementary exact decomposition of the problem into a Cramér-scale
prime-gap term and a residual prescribed-gap prime-pair term;
2. a network-free verifier which reconstructs the primorials and uses PARI/GP
APRCL to certify explicit witnesses for every \(2\leq n\leq100\);
3. an exhaustive check of the short-interval bijection for \(2\leq n\leq15\);
4. 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
5. 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=\prod_{1\leq i\leq n}p_i\). Does there always exist some prime \(p\) > with \(p_n
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: 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. The discussion thread contained the following substantive content: 1. Giorgos Kalogeropoulos, 2025-10-31: suggested the related sequence A005235; the site notes that it was subsequently added. 2. 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. 3. StijnC, 2025-09-22: compared the unrestricted difference problem with the twin-prime problem and Schinzel's hypothesis H, while noting the difficulty. 4. 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. 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. **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. 2. **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.** and PDF. Their Theorem 17 states that, for consecutive primes \(q \(Q\) satisfies \[
q\# +1 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] 3. **Cyril Banderier, “Fortunate and unfortunate primes: nearest primes from a prime factorial.”** 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] 4. **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 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] 5. **Michael M. Ross, “Sifted Symmetry and Sieve Structures of Primorial Goldbach Complements,” Zenodo record 21194754, version dated 2026-07-23.** 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. 6. OEIS A005235. Entry and 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] 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. Write Define the least nontrivial upper offset 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 [A] 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. If \(m>1\) and \(P+m\) is prime, then every prime divisor of \(m\) is at least \(r=p_{n+1}\). Consequently, 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\) For every \(n\geq4\), 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 This proves the induction. \(\square\) For an integer \(H\) with \(2 bijectionLive 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
In particular,
Proof. Given a prime \(Q\) on the left, set \(m=Q-P\). Then
\(1 \(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] For \(n\geq4\), let Then the total number \(W_n\) of #779 witnesses is exactly 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 [A] Formula (5) isolates two genuinely different possible routes: 1. 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\). 2. 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. A sufficient lemma is the pointwise boundCorollary 5: exact split of #779
4. The exact missing analytic statements
4.1 Short-gap route
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{pfor 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
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
[A]
- Every prime value \(P+m\) with \(1
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.