cp's OEIS Frontend

A023193 a(n) gives the largest number k for which there is at least one admissible k-tuple taken from [0, 1, ..., n-1] if the tuple starts with 0. Admissibility is defined in a comment.

%I A023193 #74 Feb 16 2025 08:32:34
%S A023193 1,1,2,2,2,2,3,3,4,4,4,4,5,5,5,5,6,6,6,6,7,7,7,7,7,7,8,8,8,8,9,9,10,
%T A023193 10,10,10,11,11,11,11,11,11,12,12,12,12,12,12,13,13,14,14,14,14,14,14,
%U A023193 15,15,15,15,16,16,16,16,16,16,17,17,17,17,18,18,18,18,18,18,19,19,19,19,20,20
%N A023193 a(n) gives the largest number k for which there is at least one admissible k-tuple taken from [0, 1, ..., n-1] if the tuple starts with 0. Admissibility is defined in a comment.
%C A023193 The (wrong) old name was: Largest number of pairwise coprime numbers that can occur in an interval of length n. - _Wolfdieter Lang_, Oct 10 2017
%C A023193 Conjecturally, a(n) is the largest number of primes that occurs on an infinite number of intervals of n consecutive integers. The conjecture is apparently due to Dickson; Hardy & Littlewood's Conjecture B concerns only pairs (p, p + 2n).
%C A023193 According to the link at www.opertech.com, a(3159) >= 447 > 446 = pi(3159). The k-tuples conjecture then implies that, for an infinitude of n, the interval [n+1, n+3159] includes 447 primes. For these n, pi(n+3159) >= pi(n)+447 > pi(n)+446 = pi(n)+pi(3159), contradicting the conjecture that pi(x+y) <= pi(x)+pi(y). - _David W. Wilson_, May 23 2005
%C A023193 From _Wolfdieter Lang_, Oct 10 2017: (Start)
%C A023193 The following admissibility definition is adapted from the Hensley and Richards [H-R] or Richards [R] links. A k-tuple B_k = [b_1, b_2, ..., b_k] of integers with 0 <= b_1 < b_2 < ... < b_k is admissible if, for each prime p, there exists at least one congruence class modulo p which contains none of the B_k members. Because complete residue systems modulo p are equivalent under translation one can consider the length n interval [0, 1, ..., n-1] and admissible k-tuples starting with 0. The prime p = 2 allows then only even tuple numbers from I_n = [0, 2, ..., floor((n-1)/2)]. Only primes p <= k have to be tested.
%C A023193 a(n) is then the maximal k for which there is at least one such admissible B_k tuple from the interval I_n. This function a(n) is called rho^* in (H-R) and (R). It has been given as rhobar in the Schinzel - Sierpiński link, Théorème 1, p. 201.
%C A023193 Note that there are also admissible k-tuples from members of [0, 1, ..., n-1]  which do not start with 0. Such tuples are translations of the ones starting with 0. E.g., [1, 3] is an admissible 2-tuple for any [0, 1,..., n-1] interval with n >= 3, but it is a translation of the considered [0, 2] tuple.
%C A023193 For the multiplicities of k see A047947(k), for k >= 1.
%C A023193 For the smallest k such that a(k) = n see A020497(n), for k >= 1.
%C A023193 For the number of all admissible k-tuples from the interval I_n starting with 0 see the array A292224(n, k), with k = 1..a(n), which has been given in the Engelsma link, Table 2, p. 27.
%C A023193 One of the Hardy-Littlewood conjectures (the prime tuple conjecture, see also conjecture (B) given by [H-R] and [R], and Ribenboim, hypothesis (D_1), p. 373, from the Dickson conjecture) is that there are infinitely many primes with gaps defined by any admissible B_k tuple, that is, all p, p + b_2, ..., p + b_k are prime for infinitely many primes p, for k >= 2. For k = 1 this is well known.
%C A023193 (End)
%D A023193 Douglas Hensley and Ian Richards, "On the incompatibility of two conjectures concerning primes". Analytic number theory (Proc. Sympos. Pure Math., Vol. XXIV, St. Louis Univ., St. Louis, Mo., 1972), pp. 123-127.
%D A023193 P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, NY, 1996, ch. 6, I, pp. 372-386.
%H A023193 Charles R Greathouse IV, <a href="/A023193/b023193.txt">Table of n, a(n) for n = 1..2330</a> (based on Engelsma's data)
%H A023193 L. E. Dickson, <a href="https://books.google.de/books?id=i8MKAAAAIAAJ&amp;pg=PA155&amp;redir_esc=y"> A new extension of Dirichlet's theorem on prime numbers</a>, Messenger of Math. 33 (1904) pp. 155-161.
%H A023193 Thomas J Engelsma, <a href="http://www.opertech.com/primes/k-tuples.html">k-tuple: Permissible patterns</a>
%H A023193 T. Forbes, <a href="http://anthony.d.forbes.googlepages.com/adf.htm">Prime k-tuplets</a>.
%H A023193 D. Hensley and I. Richards, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa25/aa2548.pdf">Primes in intervals</a>, Acta Arith. 25 (1974), pp. 375-391.
%H A023193 Ian Richards, <a href="http://projecteuclid.org/euclid.bams/1183535510">On the incompatibility of two conjectures concerning primes; a discussion of the use of computers in attacking a theoretical problem</a>, Bulletin of the American Mathematical Society 80:3 (1974), pp. 419-438.
%H A023193 A. Schinzel, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa7/aa711.pdf">Remarks on the paper `Sur certaines hypothèses concernant les nombres premiers'</a>, Acta Arithmetica 7 (1961), pp. 1-8 (with Dickson conjecture reference).
%H A023193 A. Schinzel and W. Sierpiński, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa4/aa432.pdf">Sur certaines hypothèses concernant les nombres premiers</a>, Acta Arithmetica 4,3 (1958), pp. 185-208, Théorème 1, p. 201; erratum 5 (1958) p. 259.
%H A023193 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-TupleConjecture.html">k-Tuple Conjecture</a>.
%H A023193 Wikipedia, <a href="https://en.wikipedia.org /wiki/Dickson&#39;s_conjecture">Dickson's conjecture</a>.
%F A023193 Conjecturally, a(n) = lim sup pi(x+n)-pi(x), where pi = A000720. This would follow from the k-tuple conjecture. - _David W. Wilson_, May 23 2005
%F A023193 a(n) = minimum m such that A008407(m) >= n. - _Max Alekseyev_, Nov 03 2008
%F A023193 Richards shows that a(n) > n/log n + kn/log^2 n + o(n/log^2 n), where k = 1 + log 2 = 1.69... . In particular, a(n) > pi(n) for large enough n. Hensley & Richards 1974 cite a result of Montgomery & Vaughan "to appear" that a(n) <= 2*pi(n) for n >= 2. - _Charles R Greathouse IV_, Apr 16 2013
%Y A023193 Cf. A008407 (minimal difference of first and last prime in a prime k-tuplet), A047947 (multiplicities), A066081 (weaker binary conjectures), A062571.
%Y A023193 Least inverse is A020497.
%Y A023193 Cf. A000720, A047947, A292224, A364678.
%K A023193 nonn,nice
%O A023193 1,3
%A A023193 _David W. Wilson_
%E A023193 Name corrected by _Wolfdieter Lang_, Oct 10 2017