A023193 - OEIS

%I #73 Feb 17 2024 18:23:11

%S 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 10,10,10,11,11,11,11,11,11,12,12,12,12,12,12,13,13,14,14,14,14,14,14,

%U 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 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 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 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 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 From _Wolfdieter Lang_, Oct 10 2017: (Start)

%C 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 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 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 For the multiplicities of k see A047947(k), for k >= 1.

%C For the smallest k such that a(k) = n see A020497(n), for k >= 1.

%C 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 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 (End)

%D 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 P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, NY, 1996, ch. 6, I, pp. 372-386.

%H 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 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 Thomas J Engelsma, <a href="http://www.opertech.com/primes/k-tuples.html">k-tuple: Permissible patterns</a>

%H T. Forbes, <a href="http://anthony.d.forbes.googlepages.com/adf.htm">Prime k-tuplets</a>.

%H 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/k-TupleConjecture.html">k-Tuple Conjecture</a>.

%H Wikipedia, <a href="https://en.wikipedia.org /wiki/Dickson&#39;s_conjecture">Dickson's conjecture</a>.

%F 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 a(n) = minimum m such that A008407(m) >= n. - _Max Alekseyev_, Nov 03 2008

%F 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 Cf. A008407 (minimal difference of first and last prime in a prime k-tuplet), A047947 (multiplicities), A066081 (weaker binary conjectures), A062571.

%Y Least inverse is A020497.

%Y Cf. A000720, A047947, A292224, A364678.

%K nonn,nice

%O 1,3

%A _David W. Wilson_

%E Name corrected by _Wolfdieter Lang_, Oct 10 2017