cp's OEIS Frontend

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

%I A364678 #47 Apr 27 2025 03:23:30
%S A364678 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 A364678 8,10,10,10,11,11,11,10,11,11,11,12,12,12,12,13,12,13,14,13,13,14,14,
%U A364678 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 A364678 Maximum number of primes between consecutive multiples of n, as permitted by divisibility considerations.
%C A364678 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 A364678 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 A364678 Conjecture 1: Every nonnegative integer appears in this sequence.
%C A364678 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 A364678 Conjecture 2 resembles the k-tuples conjecture a.k.a. the first Hardy-Littlewood conjecture, although it is not the same.
%C A364678 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 A364678 Brian Kehrig, <a href="/A364678/b364678.txt">Table of n, a(n) for n = 1..1000</a>
%H A364678 Brian Kehrig, <a href="/A364678/a364678_3.py.txt">Python code for sequence</a>
%e A364678 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 A364678 (Python) # see Links section
%Y A364678 Cf. A000010, A023193.
%Y A364678 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 A364678 nonn
%O A364678 1,4
%A A364678 _Brian Kehrig_, Aug 24 2023