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

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

Offset: 1

Author

Brian Kehrig, Aug 24 2023

Keywords

• nonn

Comments

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.

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.

Conjecture 1: Every nonnegative integer appears in this sequence.

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).

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

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

Examples

			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.
		

Links

• Brian Kehrig, Table of n, a(n) for n = 1..1000
• Brian Kehrig, Python code for sequence

Crossrefs

Cf. A000010, A023193.

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).

Programs

Python

# see Links section