## Counting locally prime numbers

In a set of ten consecutive integers, what are the possible values for the number of integers in the set that are coprime to all other integers in the set?

[SOLVED]

#### Willem solved this puzzle:

If two numbers are not coprime to each other, their common factor cannot be larger than their difference, and the maximum difference between two numbers in a set of ten consecutive integers is nine. So we only have to look at factors $$2$$, $$3$$, $$5$$ and $$7$$.

We can discount all multiples of two, three and five. These multiples may or may not overlap.

Looking at multiples of two and multiples of five, there is exactly one overlap, so that means that six numbers are discounted.

Looking at multiples of three, there are either three or four multiples. One or two of those overlap the multiples of two if there are three multiples of three. Two of those overlap the multiples of two if there are four multiples of three. There are either one or two multiples of three left. One of those may or may not overlap a multiple of five, so that's zero, one or two multiples of three left to be discounted.

Now, looking at multiples of seven, there may only be one multiple, in which case it counts, or two, in which case they will be discounted, but one of tham will overlap a multiple of two, and the other might overlap a multiple of three, so that's at most one extra discounted.

In total, between six and nine integers are discounted, so there are between one and four integers in the subset.

#### Hagen von Eitzen solved this puzzle:

The possible values are $$1$$, $$2$$, $$3$$ and $$4$$.

Let $$S = \{n, n + 1, \dots, n + 9\}$$ be a set of ten consecutive integers with smallest element $$n \in \mathbb{Z}$$ and let

$T = \{ x \in S \mid \forall y \in S \colon y \ne x \Rightarrow \gcd(x,y) = 1\}.$

If $$p$$ is a prime $$\le \frac{\#S}{2} = 5$$, then at least two elements of $$S$$ are multiples of $$p$$. Hence no element of $$T$$ has a prime factor $$p \le 5$$. Especially, we conclude that $$\# T \le 5$$ as it contains only odd numbers. But since $$\#S \gt 6$$, there is at least one element $$\equiv 3 \pmod{6}$$, i.e. an odd multiple of $$3$$. Hence we must have $$\# T \le 5 - 1 = 4$$.

On the other hand, primes $$\gt 10$$ cannot play a role as common divisors of different elements of $$S$$. $$S$$ contains at most two odd multiples of $$3$$ because the difference between the minimum and the maximum of three such numbers would be $$12$$. $$S$$ contains at most one odd multiple of $$5$$ that is not divisible by $$3$$ because the distance between consecutive odd multiples of $$5$$ is $$10$$. Similarly, $$S$$ contains at most one odd multiple of $$7$$ that is not divisible by $$3$$ or $$5$$. It follows that $$\#T \ge 5 - 1 - 1 - 2 = 1$$. Observe that the following choices of $$n$$ produce sets $$T$$ with $$1$$, $$2$$, $$3$$ and $$4$$ elements, respectively.

\begin{eqnarray*} n = 0, && T = \{1\}, \\ n = 2, && T = \{7, 11\}, \\ n = 4, && T = \{7, 11, 13\}, \\ n = 10, && T = \{11, 13, 17, 19\}. \end{eqnarray*}

If only positive integers are desired, the example $$n = 0$$ may be replaced with $$n = 210$$ and $$T = \{211\}$$. Indeed, according to the Chinese remainder theorem adding multiples of $$210$$ to $$n$$ keeps the "pattern" of $$T$$ and especially its size.

### Credit

This is an original puzzle from cotpi.

The following is a list of resources on related topics: