Problem 1204

We call a sequence of integers $0\leq a_1<\cdots <a_k$ admissible if it is missing at least one congruence class modulo every prime $p$ . Let $A(k)=\min a_k$ . Estimate $A(k)$ - in particular, is it true that

A(k)\sim k\log k?

Estimate

B(k)=\min \frac{a_1+\cdots+a_k}{k}.

Source: erdosproblems.com/1204

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open. What is known is the two-sided bound $(1/2+o(1))k\log k\le A(k)\le(1+o(1))k\log k$ and second-order refinements of the upper bound: the $k$ smallest primes above $k$ form an admissible $k$ -tuple, which gives $A(k)\le k\log k+k\log\log k-k+o(k)$ (display (149) of the Polymath paper, the sieve of Eratosthenes), and the Hensley--Richards sieve gives $A(k)\le k\log k+k\log\log k-(1+\log2)k+o(k)$ (display (150), from the 1974 Acta Arithmetica theorem that $\rho^*(x)-\pi(x)\ge(\log2-\varepsilon)x/(\log x)^2$ for large $x$ , where $\rho^*(x)$ is the size of the largest admissible tuple in an interval of $x$ integers). A 2022 announcement by Konyagin, with no published proof, claims a further second-order improvement (Current assessment). The lower bound is an application of the Brun--Titchmarsh inequality, which the site credits to Elliott (1965, not held) and the Polymath paper to the project's earlier work. The asymptotic $A(k)\sim k\log k$ is open: the Polymath paper expects $H(k)=(1+o(1))k\log k$ (p. 80) and conjectures $k\log k+k$ as an upper bound for large $k$ (p. 79); the site records that the prime tuples conjecture together with $\pi(x+y)\le\pi(x)+(1+o(1))\pi(y)$ (Problem 855) would give $A(k)\ge(1+o(1))k\log k$ ; and Hensley and Richards proved that the prime $k$ -tuples conjecture is incompatible with $\pi(x+y)\le\pi(x)+\pi(y)$ . For $B(k)$ only elementary bounds are known: $B(k)<A(k)$ , the $k$ primes above $k$ give $B(k)\le(1/2+o(1))k\log k$ , and $a_j\ge A(j)$ with the known lower bound gives $B(k)\ge(1/4-o(1))k\log k$ (the site's deduction). No source proving or refuting either asymptotic was found in the search whose scope the Current assessment records. This is a bounded negative finding, not a certificate of openness.

Er80: Erdős, P., A survey of problems in combinatorial number theory. Ann. Discrete Math. 6 (1980), 89--115; item 5 of Section 6, printed p. 108, with Elliott's paper cited on p. 109. Library home: Erdos 1980.
Po14c: Polymath, D. H. J., Variants of the Selberg sieve, and bounded intervals containing many primes. Res. Math. Sci. 1 (2014), Art. 12, 83 pp., DOI 10.1186/s40687-014-0012-7; arXiv:1407.4897 (v1 18 July 2014 to v4 22 December 2014, not held). The pages cited are the journal version's, whose sections carry no numbers; the site's "Section 10" is its section "Narrow admissible tuples" (pp. 76--81): the two-sided bound on p. 1 and p. 10, Theorem 17 on p. 10, displays (149)--(150) on p. 78, the conjectured bound on p. 79. Library home: Polymath 2014; result page display (150).
HeRi74: Hensley, D. and Richards, I., Primes in intervals. Acta Arith. 25 (1973/74), 375--391 (received 3 May 1973); the Theorem on p. 380 and Lemma 5 on p. 383. This is the paper the Polymath paper cites for the sieve of display (150); it is open access in the journal's digital library. Library home: Hensley and Richards 1974; result page Theorem.
HeRi73: Hensley, D. and Richards, I., On the incompatibility of two conjectures concerning primes. Analytic number theory (Proc. Sympos. Pure Math. 24, St. Louis 1972), Amer. Math. Soc. (1973), 123--127, DOI 10.1090/pspum/024/9945. The site's key; not held, and no open copy is known. The 1974 paper above is the authors' full account of the same sieve.
El65: Elliott, P. D. T. A., On sequences of integers. Quart. J. Math. Oxford Ser. (2) 16 (1965), 35--45, DOI 10.1093/qmath/16.1.35. Not held: the one request to the publisher's page returned HTTP 403 with a challenge page. The lower bound is quoted from the site and the Polymath paper.
OEIS: Sequence A008407 (T. Forbes, 1996; entry last modified 7 February 2026, server time), the minimal diameter of an admissible $k$ -tuple, with a table to $k=342$ and the note that later listed values are only best known; A023193 (D. W. Wilson, 1998; last modified 4 August 2026), the largest admissible tuple in an interval of $n$ integers, Hensley and Richards's $\rho^*$ ; A135311 (2007; last modified 28 June 2026), the greedy sequence with $a_1=0$ . Accessed 2026-09-18.

Problem 1204

Status

Proof claims

Discussion