Erdős problem 1055 — wave 6t

Access date: 2026-07-27 (UTC)

Claim labels used below:

• [a] elementary-rigorous;
• [b] rigorous modulo an explicitly named theorem;
• [c] plausible, heuristic, structural-unverified, or a cost estimate;
• [d] computational-only, even when the computation is exact and

independently reproducible.

0. Mandatory live-page gate

I fetched <https://www.erdosproblems.com/1055> in a rendered Bright Data browser session. Direct datacenter access was not used as the authority. The live page showed:

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

Thus neither mandatory stop condition was present. The full-page screenshot was 257,820 bytes with SHA-256 2afe7245b786ce4a0034e76b6ad5af2733232aeeaf0ece113169acfa64d2f003.

Verbatim current statement

This is copied from the live page's “View the LaTeX source” view:

A prime $p$ is in class $1$ if the only prime divisors of $p+1$ are $2$ or $3$. In general, a prime $p$ is in class $r$ if every prime factor of $p+1$ is in some class $\leq r-1$, with equality for at least one prime factor.

Are there infinitely many primes in each class? If $p_r$ is the least prime in class $r$, then how does $p_r^{1/r}$ behave?

Results and remarks listed on the live page

The page says:

• the number of primes at most \(n\) in any fixed class \(r\) is at most

\(n^{o(1)}\);

• \(p_r\) begins \(2,13,37,73,1021\), with a link to OEIS A005113;
• Erdős expected \(p_r^{1/r}\to\infty\), whereas Selfridge thought the

sequence might be bounded;

• the analogous \(p-1\) classification can also be considered;
• this is Guy's problem A18.

There were no live comments, partial results, or claimed proofs to add.

1. Primary-source and current-record audit

The cited original is P. Erdős, Problems in number theory and combinatorics, Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (1977), 35–58, MR 532690. I downloaded and checked the Rényi Institute primary scan. PDF page 19 (printed page 53) gives the definition, the infinitude question, the fixed-class \(o(n^\epsilon)\) statement, the first four \(p_r\), and the Erdős/Selfridge disagreement. The 2,507,547-byte scan has SHA-256 1f9053c64d637fb839126aa9c523d5599943b0f3dd0c602191f1aeae371e3c99.

The live page identifies R. K. Guy, Unsolved Problems in Number Theory, 3rd ed. (2004), A18, as the secondary collection. The accessible publisher front matter confirms that A18 is “The Erdős-Selfridge classification of primes,” at page 66; I did not use the book as a source for any theorem.

The current OEIS A005113 is a computational record, not a primary proof. On the access date it listed terms through class 19 and attributed the class-17/18 extensions to Jud McCranie on 2026-05-19 and class 19 on 2026-05-23. I did not import those terms or their supporting tables into the computation below. The independently obtained terms through class 18 agree; class 19 was not recomputed here.

Exact-title and exact-definition searches, searches for “Erdős-Selfridge classification”/“class-plus primes,” the OEIS references and cross-references, and bibliographic metadata searches found the original paper, Guy, OEIS records, and expository/software definitions, but no later primary research paper proving infinitude in a class or controlling \(p_r^{1/r}\). This is an honest search miss, not a proof that no unindexed literature exists.

2. Results obtained

1. [b] Every class is nonempty, modulo Dirichlet's theorem. More

strongly, for every \(r\), infinitely many primes have class at least \(r\). Thus \(p_r\) is defined for every \(r\), although exact-class infinitude remains open.

1. [a] Universal least-prime bound. For \(r\geq2\),

\[ p_r\geq 2p_{r-1}-1, \qquad\text{hence}\qquad p_r\geq 2^{r-1}+1. \] Consequently \[ \liminf_{r\to\infty}p_r^{1/r}\geq2. \] This is fully compatible with Selfridge's bounded scenario and is far short of Erdős's conjecture.

1. **[d] Exact finite theorem, with a from-scratch completeness

certificate.** \[ \boxed{\begin{aligned} (p_1,\ldots,p_{18})={}&(2,13,37,73,1021,2917,15013,49681,\\ &532801,1065601,8524807,68198461,545587687,\\ &1704961513,23869461181,288310406533,\\ &1833174628057,3666349256113). \end{aligned}} \] The last two equalities were not assumed from OEIS. The exhaustive search through class 17 uses only a one-sided filter that cannot reject a prime, and every displayed endpoint is separately certified by elementary trial division. Class 18 then follows from \[ 3666349256113=2(1833174628057)-1 \] and the universal lower bound.

1. [a] Exact sufficient lemma isolating the infinitude obstruction. If

\(q\) has class \(r-1\) and \[ 2^a3^bq-1 \] is prime for infinitely many pairs \((a,b)\), then class \(r\) contains infinitely many primes. For \(q=1\), this is exactly the class-1 question. Even that case—infinitely many second-kind Pierpont primes \(2^a3^b-1\)—is not known.

3. Structural proofs

Let \(h(p)\) denote the class of the prime \(p\). For \(p>3\), the definition is equivalently

with the maximum absent exactly in class 1.

3.1 Nonemptiness of all classes

The prime \(5\) has class 1. Suppose \(a>3\) is a prime of class \(r\). Dirichlet's theorem on primes in arithmetic progressions gives infinitely many primes

For each such \(P\), \(a\mid P+1\), so (1) gives \(h(P)\geq r+1\). If \(h(P)=s>r+1\), repeatedly choose the factor of the preceding prime plus one which realizes the maximum in (1). This produces primes of classes \(s-1,s-2,\ldots,r+1\). In particular, class \(r+1\) is nonempty. Induction proves nonemptiness of every class. Fixing \(a\) also proves that infinitely many primes lie in the union of classes \(r+1,r+2,\ldots\). This is [b], with Dirichlet's theorem as the only non-elementary input.

The step does not yield infinitely many primes of class exactly \(r+1\): uncontrolled prime factors of \((P+1)/a\) may have higher class. That is the precise point at which Dirichlet's theorem stops helping.

3.2 Universal lower bound

Let \(p\) have class \(r\geq2\). There is a prime \(q\mid p+1\) of class \(r-1\). For \(r=2\), since \(p\) is not already in the exceptional base class, \(q\) may be chosen \(>3\); for \(r>2\) this is automatic. Thus \(p,q\) are odd and

for an even integer \(m\geq2\). Hence

Writing \(x_r=p_r-1\) gives \(x_r\geq2x_{r-1}\), and since \(x_1=1\), \(p_r\geq2^{r-1}+1\). This proves all claims in item 2 [a].

3.3 Thin-semigroup reduction

If \(q\) has class \(r-1\) and \(P=2^a3^bq-1\) is prime, then the only prime factors of \(P+1\) are \(2,3,q\). Therefore \(P\) has class exactly \(r\). For \(q=1\), the same observation is precisely the class-1 definition. This proves item 4 [a].

4. Exhaustive finite certificate

4.1 Why the search is complete

Set

Let \(F(n)\) be the strong probable-prime filter to base 2, preceded by trial division by the primes through 37. The only property used is

No converse is assumed.

Construct supersets \(A_r\) as follows.

• \(A_1\) contains every \(2^a3^b-1\leq B_1\) which passes \(F\).
• For \(r\geq2\), for every \(q\in A_{r-1}\) and every even \(m\) with

\(mq-1\leq B_r\), insert \(mq-1\) into \(A_r\) when it passes \(F\) and every prime factor of \(m\) has exact class at most \(r-1\).

• At \(r=2\), witnesses \(q=2,3\) are omitted because every genuine class-2

prime has a class-1 factor \(q>3\).

All multiplier factorizations and their prime classes are computed by a linear smallest-prime-factor sieve through \(11{,}188{,}811\); the largest possible multiplier is

Inductively,

Indeed, for a genuine class-\(r\) prime \(p\), choose a class-\((r-1)\) factor \(q\mid p+1\). Then

all prime factors of \(m\) have class at most \(r-1\), \(q\in A_{r-1}\) by induction, and \(p\) passes \(F\) by (3). Thus the program may retain extra composites, but it cannot miss a prime in the searched class and interval.

This one-sided design is useful: the finite lower bounds do not depend on a published deterministic Miller–Rabin cutoff or on trusting a black-box primality routine.

4.2 Search transcript

The third column below is the number of base-2-filter survivors in \(A_r\), not the number of primes and not the number of genuine class-\(r\) primes. It is included as a reproducibility fingerprint.

The least survivor at every stage was then proved prime and assigned the displayed class by a separate trial-division factorization of both \(p\) and the complete recursive \(p+1\) factor tree. Trial primes were generated from scratch through

Combining these exact endpoint checks with (4) proves the minima through class 17 [d].

Finally, trial division proves \(3666349256113\) prime, and

It therefore has class 18, while Section 3.2 rules out any smaller class-18 prime. This proves the class-18 term [d].

5. Code and independent rerun

The standalone verifier is erdos1055_wave6t_verify.py. It contains both independent components:

1. a pure-Python Eratosthenes sieve, exact trial division, and recursive

class calculation for all 18 endpoints;

1. a self-contained C++17 one-sided exhaustive search, compiled in a

temporary directory and rerun from scratch.

The separate development implementation is erdos1055_exact_search.cpp. Neither program downloads or reads OEIS data.

Core exhaustive step:

A[1] = {2^a 3^b - 1 <= B[1] : passes_one_sided_filter}
for r = 2,...,17:
    for q in A[r-1]:
        for even m with m*q - 1 <= B[r]:
            if filter(m*q - 1) passes
               and every prime factor s of m has h(s) <= r-1:
                   insert m*q - 1 into A[r]

Command actually run:

/usr/bin/time -v python runs/erdos1055_wave6t_verify.py

Output:

exact trial-division class certificates: OK
one-sided exhaustive lower-bound search: OK
least primes in classes 1..18:
2,13,37,73,1021,2917,15013,49681,532801,1065601,8524807,68198461,545587687,1704961513,23869461181,288310406533,1833174628057,3666349256113
VERIFIED elapsed_seconds=98.567

Measured resources: 97.97 user CPU seconds, 98.72 wall seconds, one core, 589,592 KiB peak resident memory, exit status 0.

Code hashes at the time of the run:

e8a4bace2472e707738af24d5112b3df253c85b8757849a5c96d2c01fac95a1f  erdos1055_exact_search.cpp
03fa2d738ca9eca5b728f1d7f96cfbbc478645fe9d1fdb3b7c28e954a089d02e  erdos1055_wave6t_verify.py

6. Exact wall

Infinitude

Class 1 already asks for infinitely many primes among the two-parameter exponential sequence \(2^a3^b-1\). Up to \(x\) there are only \(O((\log x)^2)\) candidates. Dirichlet's theorem is inapplicable because the modulus changes with the candidate; ordinary sieve methods do not resolve primality in this thin sequence. [c] This is the first missing prime-values lemma, before recursion enters.

For higher classes, the sufficient lemma

for one class-\((r-1)\) prime \(q\) would settle exact-class infinitude. Dirichlet supplies infinitely many primes \(P\equiv-1\pmod q\), but gives no control over the class of prime factors of \((P+1)/q\). The missing input is exactly smooth/class-bounded cofactor control, not merely a prime in an arithmetic progression.

Growth

The page's \(n^{o(1)}\) estimate is for each fixed \(r\). It has no stated uniform dependence on \(r\), so it cannot imply a superexponential lower bound for \(p_r\). Erdős's conjecture requires

whereas the elementary recursion proves only \(\log p_r\geq(r-1)\log2+o(1)\). A uniform-in-\(r\) anti-concentration or prime-avoidance lemma strong enough to bridge that gap is the precise missing ingredient.

Next exact computation

Using the current OEIS class-19 candidate as a search ceiling but not as an assumption, the same certificate would start with

Stage 2 alone has 165,144,832 one-sided candidates, versus 18,349,405 in the completed run, and needs a smallest-factor table through 100,699,290. Later survivor sets dominate memory. [c] A straightforward version is estimated at 0.3–1 core-hour and several GB of RAM; independently certifying the proposed class-20 ceiling begins with 956,267,372 stage-2 candidates and is plausibly a 2–10 core-hour, multi-GB job. Neither was run on this box.

The open infinitude and asymptotic questions are not closed by any finite table.

PARTIAL: modulo Dirichlet every class is nonempty and infinitely many primes lie at or above each class; an independent exact certificate gives \(p_1,\ldots,p_{18}\), while exact-class infinitude and the behavior of \(p_r^{1/r}\) remain open.