Are there infinitely many primes $p=2^kq+1$ (or $2^k3^\ell q+1$) with $q$ prime? (Erdős #1065)
Statement
Are there infinitely many primes $p$ that can be written as $p=2^{k}q+1$ for some prime $q$ and integer $k\geq 0$? More generally, are there infinitely many primes of the form $p=2^{k}3^{\ell}q+1$ for some prime $q$ and integers $k,\ell\geq 0$? (Here $q$ ranges over primes and $k,\ell$ over non-negative integers.)
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred, else a full written proof) that infinitely many primes have the form $2^{k}q+1$ with $q$ prime — or the stronger $2^{k}3^{\ell}q+1$ form — OR a proof that only finitely many do. ADVANCES, each independently checkable: a proof of infinitude under a stated standard hypothesis (e.g. a prime $k$-tuples / Hardy–Littlewood or Bombieri–Vinogradov-type input), clearly flagged as conditional; a proven lower bound on the counting function of such primes stronger than what is currently known; or a reproducible large-scale computation extending the enumeration of such primes to a new height with the sieve code and the counting-function data (state the previous verified height in words). Deliver the proof (conditional clearly flagged) or the sieve program plus the attained height and counts.
Background
An Erdős question recorded as problem B46 in Guy's Unsolved Problems in Number Theory [Gu04]; listed as open on erdosproblems.com/1065 (fetched 2026-07-21, status 'open'). Every odd prime $p$ has $p-1=2^{a}m$ with $m$ odd, so the first question asks whether the odd part $m$ (or, allowing a further factor $3^{\ell}$, the part of $p-1$ coprime to $6$) is itself prime for infinitely many $p$ — a joint smoothness-and-primality condition on $p-1$. Heuristically the density of such primes is positive, but a proof is beyond current technology: it is at least as hard as showing infinitely many primes $p$ have $p-1=2q$ with $q$ prime (a Sophie-Germain-type statement). Relevant sequences are OEIS A074781 and A339465, and a Lean-formalised statement is available in the formal-conjectures project. This is the existence companion to the Sierpiński-type question of whether some fixed $m$ makes $2^{k}3^{\ell}m+1$ never prime (Erdős #203, erdosproblems.com/203). Attacker's tool: large-scale sieving to compute the counting function of such primes and compare it to the Hardy–Littlewood heuristic constant$\times x/\log^{2}x$ (extending A074781 / A339465), plus any sieve or transference input aimed at an unconditional or conditional infinitude lower bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1065 (T. F. Bloom) | website |
| REF-02 | OEIS A074781 — primes of the form 2^k*q+1 | website |
| REF-03 | OEIS A339465 — related primes of the form 2^k*3^l*q+1 | website |
| REF-04 | Lean formalisation of Erdős #1065 (formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.