

A023193


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


9



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, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 14, 14, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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
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).
According to the link at www.opertech.com, a(3159) >= 447 > 446 = pi(3159). The ktuples 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
From Wolfdieter Lang, Oct 10 2017: (Start)
The following admissibility definition is adapted from the Hensley and Richards [HR] or Richards [R] links. A ktuple 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, ..., n1] and admissible ktuples starting with 0. The prime p = 2 allows then only even tuple numbers from I_n = [0, 2, ..., floor((n1)/2)]. Only primes p <= k have to be tested.
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 (HR) and (R). It has been given as rhobar in the Schinzel  Sierpiński link, Théorème 1., p. 201.
Note that there are also admissible ktuples from members of [0, 1, ..., n1] which do not start with 0. Such tuples are translations of the ones starting with 0. E.g., [1, 3] is an admissible 2tuple for any [0, 1,..., n1] interval with n >= 3, but it is a translation of the considered [0, 2] tuple.
For the multiplicities of k see A047947(k), for k >= 1.
For the smallest k such that a(k) = n see A020497(n), for k >= 1.
For the number of all admissible ktuples 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.
One of the HardyLittlewood conjectures (the prime tuple conjecture, see also conjecture (B) given by [HR] 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.
(End)


REFERENCES

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. 123127.
P. Ribenboim, The New Book of Prime Number Records, SpringerVerlag, NY, 1996, ch. 6, I, p. 372  386.


LINKS

Charles R Greathouse IV, Table of n, a(n) for n = 1..2330 (based on Engelsma's data)
L. E. Dickson, A new extension of Dirichlet's theorem on prime numbers, Messenger of Math. 33 (1904) pp. 155161.
Thomas J Engelsma, ktuple: Permissible patterns
T. Forbes, Prime ktuplets.
D. Hensley and I. Richards, Primes in intervals, Acta Arith. 25 (1974), pp. 375391.
Ian Richards, On the incompatibility of two conjectures concerning primes; a discussion of the use of computers in attacking a theoretical problem, Bulletin of the American Mathematical Society 80:3 (1974), pp. 419438.
A. Schinzel, Remarks on the paper `Sur certaines hypothèses concernant les nombres premiers', Acta Arithmetica 7 (1961), pp. 18 (with Dickson conjecture reference).
A. Schinzel and W. Sierpiński, Sur certaines hypothèses concernant les nombres premiers, Acta Arithmetica 4,3 (1958), pp. 185208, Théorème 1, p. 201; erratum 5 (1958) p. 259.
Eric Weisstein's World of Mathematics, Prime kTuples Conjecture.
Wikipedia, Dickson's conjecture.


FORMULA

Conjecturally, a(n) = lim sup pi(x+n)pi(x), where pi = A000720. This would follow from the ktuple conjecture.  David W. Wilson, May 23 2005
a(n) = minimum m such that A008407(m) >= n.  Max Alekseyev, Nov 03 2008
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


CROSSREFS

Cf. A008407 (minimal difference of first and last prime in a prime ktuplet), A047947 (multiplicities), A066081 (weaker binary conjectures), A062571.
Least inverse is A020497.
Cf. A000720, A047947, A292224.
Sequence in context: A257684 A098424 A098428 * A096605 A189671 A109497
Adjacent sequences: A023190 A023191 A023192 * A023194 A023195 A023196


KEYWORD

nonn,nice,changed


AUTHOR

David W. Wilson


EXTENSIONS

Name corrected by Wolfdieter Lang, Oct 10 2017


STATUS

approved



