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.

2. [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.

3. **[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.

4. [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.

| \(r\) | \(B_r\) | \(|A_r|\) | least survivor |

|---:|---:|---:|---:|

| 1 | 27,972,025 | 50 | 2 |

| 2 | 55,944,050 | 17,878 | 13 |

| 3 | 111,888,100 | 862,971 | 37 |

| 4 | 223,776,200 | 4,698,914 | 73 |

| 5 | 447,552,400 | 7,963,392 | 1,021 |

| 6 | 895,104,799 | 7,228,660 | 2,917 |

| 7 | 1,790,209,598 | 4,537,375 | 15,013 |

| 8 | 3,580,419,196 | 2,208,274 | 49,681 |

| 9 | 7,160,838,391 | 881,482 | 532,801 |

| 10 | 14,321,676,782 | 290,596 | 1,065,601 |

| 11 | 28,643,353,564 | 80,532 | 8,524,807 |

| 12 | 57,286,707,127 | 19,550 | 68,198,461 |

| 13 | 114,573,414,254 | 4,030 | 545,587,687 |

| 14 | 229,146,828,508 | 731 | 1,704,961,513 |

| 15 | 458,293,657,015 | 119 | 23,869,461,181 |

| 16 | 916,587,314,029 | 11 | 288,310,406,533 |

| 17 | 1,833,174,628,057 | 1 | 1,833,174,628,057 |

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;

2. 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.