ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1065 · PARTIAL

Erdős problem 1065 — wave w031

Date: 2026-07-29 UTC

Claim labels

congruences.

stated standard theorem.

unproved uniformity.

rerun as described, but not a proof of infinitude.

Bibliographic and live-site observations are reported as such rather than given mathematical claim labels.

0. Mandatory live-page gate

I fetched the live page, its LaTeX-source view, and the discussion thread through the Bright Data browser route on 2026-07-29. This was done before any mathematics.

Exact current statement

The following is verbatim from the live page's LaTeX-source view:

Are there infinitely many primes \(p\) such that \(p=2^kq+1\) for some prime \(q\) and \(k\geq 0\)? Or \(p=2^k3^lq+1\)?

The page then says, verbatim:

This is mentioned in problem B46 of Guy's collection \(\cite{Gu04}\).

The linked formal statement quantifies \(k,l\) over natural numbers and spells the second question out with \(k,l\geq0\). I use that intended reading below.

Status and collision decision

The live page showed:

Thus neither stop condition was present, so I proceeded.

The one live comment

The 01 November 2025 comment says:

  1. Bateman--Horn predicts “yes” for every fixed \(k>0,l\), in particular

for Sophie Germain primes.

  1. In the opposite direction, \(q=271129\) is said to satisfy that

\(2^nq+1\) is never prime, with a link to Sierpiński numbers.

The forum warns that comments are unverified. I therefore did not use either assertion as ground truth. Section 5 independently reconstructs and checks the complete six-prime cover for \(271129\).

1. Literature audit

I searched the exact statement, equivalent largest-prime-factor wording, Guy B46, both linked OEIS sequences, the Bateman--Horn specialization, and the \(271129\) covering claim.

  1. Guy. The official Springer record verifies Richard K. Guy,

Unsolved Problems in Number Theory, third edition, 2004, DOI 10.1007/978-0-387-26677-0. The live page identifies the question as B46, “The largest prime factor of \(n\).” I found only table-of-contents/previews of the relevant edition, not an inspectable full copy of page 154, so I do not attribute more to B46 than the live page does.

  1. The linked sequences.

OEIS A074781 is the first set in the question. OEIS A339465 is exactly the additional part of the second set; the equivalence is proved in Section

  1. A339465 explicitly says its infinitude is unknown. These are database

records, not proofs.

  1. Bateman--Horn. P. T. Bateman and R. A. Horn,

“A heuristic asymptotic formula concerning the distribution of prime numbers,” Mathematics of Computation 16 (1962), 363--367, DOI 10.1090/S0025-5718-1962-0148632-7, is the original paper. Applied to \(t\) and \(at+1\), it predicts infinitely many simultaneous prime values for every fixed even \(a\). This remains conjectural here.

  1. The covering result. W. Sierpiński,

“Sur un problème concernant les nombres \(k2^n+1\)”, Elemente der Mathematik 15 (1960), 73--74, proves the existence of infinitely many covering coefficients. More specifically, J. L. Selfridge's solution to Monthly Problem 4995, American Mathematical Monthly 70 (1963), 100--101, stable record, explicitly gives the covering set \(\{3,5,7,13,17,241\}\) for \(271129\). Wilfrid Keller's later computational paper, “Factors of Fermat numbers and large primes of the form \(k2^n+1\),” Mathematics of Computation 41 (1983), 661--673, DOI 10.1090/S0025-5718-1983-0717710-7, also discusses this coefficient.

  1. Nearby but not a solution. The OEIS cross-reference P. Erdős and

C. Pomerance, “On the largest prime factors of \(n\) and \(n+1\)”, Aequationes Mathematicae 17 (1978), 311--321, is a genuine primary paper, but its theorems concern typical comparisons of largest prime factors of consecutive integers; it does not provide the needed simultaneous-prime lower bound. Graeme Cohen, “On a conjecture of Mąkowski and Schinzel”, Colloquium Mathematicum 74 (1997), 1--8, uses primes from A074781 in a different \(\sigma\)-\(\varphi\) problem and likewise does not prove infinitude. A 2024 search hit titled “Numbers of the form \(p-1\) where \(p\) is prime” uses \(q\) for a square-free integer, not a prime, so its asymptotics do not address this question.

Exact-phrase, formula, citation, and largest-prime-factor searches found no primary paper claiming either infinitude statement. That is a documented search miss, not proof that no such paper exists.

2. Exact factorization reduction

Let

\[ \begin{aligned} \mathcal A_1&=\{p\text{ prime}:p=2^kq+1 \text{ for some prime }q,\ k\geq0\},\\ \mathcal A_2&=\{p\text{ prime}:p=2^k3^lq+1 \text{ for some prime }q,\ k,l\geq0\}. \end{aligned} \]

Canonical tests

(a) Every \(p\in\mathcal A_1\) is odd. Write

\[ p-1=2^u m,\qquad m\ \text{odd}. \]

Then

\[ p\in\mathcal A_1\quad\Longleftrightarrow\quad m=1\ \text{or}\ m\text{ is prime}. \tag{1} \]

Indeed, if \(m>1\), unique factorization forces \(q=m\) and \(k=u\). If \(m=1\), take \(q=2\) and \(k=u-1\). The converse is immediate.

Similarly write

\[ p-1=2^u3^v r,\qquad (r,6)=1. \]

Then

\[ p\in\mathcal A_2\quad\Longleftrightarrow\quad r=1\ \text{or}\ r\text{ is prime}. \tag{2} \]

For \(r>1\), unique factorization forces \(q=r\). For \(r=1\), take \(q=2,k=u-1,l=v\). These equivalences are the classification used by the finite checker.

Why A339465 is exactly the added set

(a) Suppose (2) holds but (1) does not. If \(r>1\), then \(r>3\) is prime and necessarily \(v\geq1\); the greatest prime factor of \(p-1\) is \(r\), and

\[ \frac{p-1}{P(p-1)}=2^u3^v,\qquad u,v\geq1. \]

If \(r=1\), failure of (1) means \(v\geq2\); now \(P(p-1)=3\) and the quotient is \(2^u3^{v-1}\), again with both exponents positive. Reversing the argument proves

\[ \mathcal A_2\setminus\mathcal A_1=\mathrm{A339465}. \tag{3} \]

The precise prime-pair core

For even \(a\), define

\[ S_a(y)=\#\{q\leq y:q>3\text{ prime and }aq+1\text{ prime}\}. \tag{4} \]

Apart from the explicitly classifiable \(2,3\)-smooth cases, (2) gives the exact disjoint reduction

\[ A_2(x)=E_{2,3}(x)+ \sum_{\substack{u\geq1,\ v\geq0\\2^u3^v\leq(x-1)/5}} S_{2^u3^v}\!\left(\frac{x-1}{2^u3^v}\right), \tag{5} \]

where \(E_{2,3}(x)\) counts prime \(p\leq x\) with \(p-1=2^u3^v\). There are only \(O((\log x)^2)\) such candidates. The analogous first-set decomposition uses \(v=0\), plus the \(p-1=2^u\) cases.

Thus the unsolved part is not factorization: it is a lower bound for the two linear forms \(q\) and \(aq+1\).

3. A uniform upper bound

The following records exactly what ordinary sieve machinery can prove and where its direction stops.

Uniform two-form sieve

(b), using the standard two-dimensional Selberg upper-bound sieve. For \(a=2^u3^v\), \(u\geq1,v\geq0\), uniformly in \(a\) and \(y\geq3\),

\[ S_a(y)\ll \frac{y}{(\log y)^2}+1. \tag{6} \]

To check the hypotheses, sieve the product \(n(an+1)\). For every prime \(\rho\geq5\), exactly two residue classes modulo \(\rho\) are forbidden because \(\rho\nmid a\). At \(\rho=2,3\), one or two classes are forbidden. Consequently the dimension is two and the local singular factor is bounded uniformly over this family of \(a\); the Selberg upper-bound sieve gives (6). No distribution theorem for primes is being hidden here: this is an upper sieve on integer \(n\).

Summing over all exponents

(a) The reciprocal coefficients satisfy

\[ \sum_{u\geq1,v\geq0}\frac1{2^u3^v}=\frac32. \tag{7} \]

For \(Y\geq2\), a direct geometric-tail split gives

\[ \sum_{\substack{u\geq1,v\geq0\\2^u3^v>Y}} \frac1{2^u3^v}\ll\frac{\log Y}{Y}. \tag{8} \]

For completeness, fix \(v\) with \(3^v\leq Y\). The tail over \(u\) is at most \(2\cdot3^v/Y\), so after multiplication by \(3^{-v}\) it contributes at most \(2/Y\); there are \(O(\log Y)\) such \(v\). The remaining \(3^{-v}\) tail is \(O(1/Y)\).

Split (5) at \(a=\sqrt x\). For \(a\leq\sqrt x\), (6), (7), and \(\log(x/a)\geq\tfrac12\log x\) give \(O(x/\log^2x)\). For \(a>\sqrt x\), the trivial bound \(S_a(x/a)\leq x/a\) and (8) give \(O(\sqrt x\log x)\). The smooth exceptional term is \(O((\log x)^2)\). Therefore

\[ \boxed{A_2(x)\ll\frac{x}{(\log x)^2}},\qquad \boxed{A_1(x)\ll\frac{x}{(\log x)^2}}. \tag{9} \]

The second assertion also follows from \(\mathcal A_1\subseteq\mathcal A_2\). This is a rigorous density-zero upper bound, modulo the named standard upper-sieve theorem. It has the conjecturally correct order but supplies no positive lower bound.

4. Exact census through \(10^8\)

Define \(A_i(x)=|\mathcal A_i\cap[1,x]|\).

Complete table

(d) Exact finite computation.

| \(x\) | \(\pi(x)\) | \(A_1(x)\) | \(A_2(x)\) | \(A_2(x)-A_1(x)\) | |---:|---:|---:|---:|---:| | \(10\) | 4 | 3 | 3 | 0 | | \(10^2\) | 25 | 15 | 23 | 8 | | \(10^3\) | 168 | 59 | 117 | 58 | | \(10^4\) | 1,229 | 257 | 580 | 323 | | \(10^5\) | 9,592 | 1,470 | 3,264 | 1,794 | | \(10^6\) | 78,498 | 9,287 | 20,479 | 11,192 | | \(10^7\) | 664,579 | 65,061 | 140,205 | 75,144 | | \(10^8\) | 5,761,455 | 481,051 | 1,021,854 | 540,803 |

The maximum consecutive gap in \(\mathcal A_1\cap[1,10^8]\) is

\[ 78\,199\,097-78\,196\,487=2610, \]

and the maximum gap in \(\mathcal A_2\cap[1,10^8]\) is

\[ 58\,430\,467-58\,429\,139=1328. \]

These are finite observations, not bounded-gap claims.

Exponent distribution

For \(\mathcal A_1\), use the unique representation exponent \(k=u\) when the odd part is prime, and \(k=u-1,q=2\) when \(p-1\) is a power of two. The exact \(p\leq10^8\) counts are:

| \(k\) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | count | 1 | 229,568 | 119,718 | 62,675 | 32,651 | 17,128 | 9,078 | 4,793 | 2,500 | 1,353 | 745 |

| \(k\) | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | count | 382 | 212 | 104 | 66 | 33 | 16 | 12 | 7 | 5 | 3 | 1 |

For the 540,803 added terms, their exact distribution by \(v=\nu_3(p-1)\) is:

| \(v\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |---:|---:|---:|---:|---:|---:|---:|---:|---:| | count | 345,258 | 124,223 | 45,043 | 16,567 | 6,059 | 2,281 | 846 | 327 |

| \(v\) | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | |---:|---:|---:|---:|---:|---:|---:|---:|---:| | count | 131 | 43 | 15 | 7 | 0 | 1 | 1 | 1 |

The first displayed terms of both live-page-linked OEIS sequences agree entry-for-entry with the recomputation; those prefixes are only sanity checks and are not used as an oracle.

Heuristic comparison

Let

\[ C_2=\prod_{\rho>2}\frac{\rho(\rho-2)}{(\rho-1)^2} \]

be the twin-prime product. For fixed even \(a\), Bateman--Horn predicts

\[ S_a(y)\sim 2C_2\!\!\prod_{\substack{\rho\mid a\\\rho>2}} \frac{\rho-1}{\rho-2} \int_2^y\frac{dt}{\log t\,\log(at+1)}. \tag{10} \]

For \(a=2^u3^v\), the finite product is \(1\) for \(v=0\) and \(2\) for \(v>0\). Formally summing the fixed-\(a\) main terms gives

\[ A_1(x)\stackrel{?}{\sim}2C_2\frac{x}{\log^2x},\qquad A_2(x)\stackrel{?}{\sim}4C_2\frac{x}{\log^2x}. \tag{11} \]

(c) Equation (11) is only structural evidence: fixed-polynomial Bateman--Horn does not itself justify interchanging the limit and the infinite sum over \(u,v\). At \(10^8\), the observed normalized quantities are

\[ A_1(x)\frac{\log^2x}{x}=1.632309368,\qquad A_2(x)\frac{\log^2x}{x}=3.467370107, \]

and both have decreased steadily at the tabulated powers of ten from \(x=10^3\) onward. This is evidence, not a theorem.

5. Explicit cover for the comment's \(q=271129\)

The checker trial-divides \(271129\) by every possible divisor through \(\lfloor\sqrt{271129}\rfloor=520\) and finds none, so it is prime. The following certificate proves the stronger all-exponent assertion.

| divisor \(r\) | \(271129\bmod r\) | \(\operatorname{ord}_r(2)\) | exponents covered | |---:|---:|---:|:---| | 3 | 1 | 2 | \(n\equiv1\pmod2\) | | 5 | 4 | 4 | \(n\equiv0\pmod4\) | | 7 | 5 | 3 | \(n\equiv2\pmod3\) | | 13 | 1 | 12 | \(n\equiv6\pmod{12}\) | | 17 | 13 | 8 | \(n\equiv6\pmod8\) | | 241 | 4 | 24 | \(n\equiv10\pmod{24}\) |

(a) In each row,

\[ 271129\cdot2^n+1\equiv0\pmod r \]

for the indicated class; the orders make the implication periodic. Modulo 24, odd residues are covered by the first row, while the twelve even residues are covered as follows:

\[ \begin{array}{c|c} \text{row}&\text{even residues covered modulo }24\\ \hline r=5&0,4,8,12,16,20\\ r=7&2,8,14,20\\ r=13&6,18\\ r=17&6,14,22\\ r=241&10. \end{array} \]

Their union is every even residue. Each divisor is smaller than \(271129\cdot2^n+1\), including at \(n=0\), so every such number is composite. Thus the page comment's example is fully verified from scratch:

\[ \boxed{271129\text{ is prime, but }271129\cdot2^n+1 \text{ is composite for every }n\geq0.} \]

This refutes a possible “every prime \(q\) works for some \(k\)” route, but does not refute either infinitude question, whose quantifiers run over \(p\) and allow \(q\) to vary.

6. Reproduction and independent checks

The standalone verifier is erdos1065_wavew031_reverify.py. Its SHA-256 is

ca7dfc22444d4b673315fa09e5d6b40f2e338d102d2c764a8b70cd02ab9549b4

Run from the repository root:

python3 runs/erdos1065_wavew031_reverify.py

It uses no third-party packages or downloaded tables. It performs:

  1. a monolithic odd-only Eratosthenes sieve through \(10^8\);
  2. a separately coded segmented sieve whose base primes are generated by

trial division;

  1. exact equality of the two 50-million-entry prime bit maps and of the

5,761,455-prime arrays, including a SHA-256 digest;

  1. two complete classifications using (1) and (2);
  2. a third, direct generator over every allowed \(2^kq+1\) and

\(2^k3^lq+1\), deduplicated and compared to both classified sets;

  1. OEIS-prefix checks, hard-coded final counts/gaps/tails, and the complete

24-residue covering check for \(271129\).

The core classification is:

n = p - 1
u = (n & -n).bit_length() - 1
oddpart = n >> u
in_A1 = oddpart == 1 or is_prime(oddpart)

v = 0
rest = oddpart
while rest % 3 == 0:
    rest //= 3
    v += 1
in_A2 = rest == 1 or is_prime(rest)

The exact saved run ended:

100000000,5761455,481051,1021854,540803
prime_sha256_le_u32=0feea6e7805b8bae663ecadd180f8ea94061ff0b16d6f9da2472fbe2e6d5cbb5
C1_max_gap=(2610, 78196487, 78199097)
C2_max_gap=(1328, 58429139, 58430467)
cover_271129=3:n=1(mod 2),5:n=0(mod 4),7:n=2(mod 3),13:n=6(mod 12),17:n=6(mod 8),241:n=10(mod 24)
timing_seconds=monolithic:0.733,segmented:0.205,census1:9.412,census2:9.279,crosschecks:7.030,total:26.659
ALL CHECKS PASSED
TIME_ELAPSED=27.05 MAXRSS_KB=257572

7. The exact wall

The first set contains the fixed case \(k=1\), namely safe primes \(p=2q+1\). Proving infinitely many of those alone would settle both questions, but the first question is not logically equivalent to the Sophie Germain conjecture: in principle, its infinitely many witnesses could use unbounded \(k\).

The exact missing analytic input exposed by (5) is a lower bound such as

\[ \sum_{\substack{a=2^u3^v\leq\sqrt x\\u\geq1,v\geq0}} S_a(x/a)\gg\frac{x}{\log^2x}, \tag{12} \]

or, much more strongly than necessary, \(S_a(y)\to\infty\) for one fixed even \(a\). The Selberg sieve proves the matching-direction upper bound (6) but cannot turn it into (12): requiring both remaining factors to have odd prime-factor parity is the classical sieve parity obstruction. This is the precise missing lemma, not a shortage of small cases.

The present verifier scales linearly in the cutoff. Extrapolating its measured run, \(10^{10}\) would cost roughly \(0.75\) one-core hours and 15--25 GB with the deliberately duplicated data structures; it was not run. A count-only segmented implementation could reduce memory, but no finite cutoff supplies the uniform lower bound (12).

PARTIAL: Proved the canonical reduction and a uniform \(O(x/\log^2x)\) upper bound modulo the standard Selberg upper sieve; exactly enumerated 481,051 first-form and 1,021,854 second-form primes through \(10^8\) with three-way verification; and gave a complete cover proving the prime \(271129\) never yields \(2^nq+1\) prime. Infinitude remains blocked by a prime-pair lower bound across \(a=2^k3^l\), i.e. the sieve parity barrier.

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