A364678 - OEIS

%I #43 Apr 02 2024 14:34:48

%S 0,1,1,2,2,2,2,3,3,4,4,4,4,4,4,5,5,6,6,6,5,7,7,6,7,7,7,7,8,7,8,9,8,10,

%T 8,10,10,10,11,11,11,10,11,11,11,12,12,12,12,13,12,13,14,13,13,14,14,

%U 15,15,14,15,15,15,16,15,15,16,16,17,16,17,18,18,18,18,18,17,19,19,19,19,20,20,19,19,20,21,21

%N Maximum number of primes between consecutive multiples of n, as permitted by divisibility considerations.

%C Alternatively: a(n) = the maximum number of elements of an admissible k-tuple strictly contained in (0,n) such that all elements are relatively prime to n. Recall that an admissible tuple is defined as a tuple of integers with the property that all primes p have at least one residue class that has no intersection with the tuple.

%C For n > 1, we have a(n) <= A023193(n-1), with equality if (but not only if) n is prime or a power of 2. The smallest n for which it is not an equality is n=14.

%C Conjecture 1: Every nonnegative integer appears in this sequence.

%C Conjecture 2: For all n, there is an infinitude of k's such that there are a(n) primes between n*k and n*(k+1).

%C Conjecture 2 resembles the k-tuples conjecture a.k.a. the first Hardy-Littlewood conjecture, although it is not the same.

%C A notable value is a(35) = 8. Compare with A000010(210) = 48. This says that between any two consecutive multiples of 210 the 48 values that are not divisible by 2, 3, 5 or 7 are equally distributed between 6 equal divisions of 210; that is, 8 are in the interval [0, 34], 8 in the interval [35, 69], etc. - _Peter Munn_, Feb 16 2024

%H Brian Kehrig, <a href="/A364678/b364678.txt">Table of n, a(n) for n = 1..1000</a>

%H Brian Kehrig, <a href="/A364678/a364678_3.py.txt">Python code for sequence</a>

%e Between two multiples of 15 (n and n+15), only n+1, n+2, n+4, n+7, n+8, n+11, n+13, and n+14 could possibly be prime based on divisibility by 3 and 5. However, 4 of these are even and 4 are odd, so at most 4 of them can be prime. Thus, a(15)=4.

%o (Python) # see Links section

%Y Cf. A000010, A023193.

%Y Multiples of n following which the maximum number of primes occur for particular n: A005097 (2), A144769 (3), A123986 (4), A056956	(6), A007811 (10), A123985 (12), A309871 (18).

%K nonn

%O 1,4

%A _Brian Kehrig_, Aug 24 2023