to count the intervals

Question

A finite set of two or more consecutive natural numbers is called a "co-prime interval" if there is no number in it that is co-prime to all other numbers in the set.

Given a range [A, B], I would like to count the number of co-prime intervals completely contained in it. i.e., I want to know how many different pairs (a, b) exist such that A ≤ a < b ≤ B and the set {a, a+1, ..., b} is a co-prime interval.

test cases:

Input:

4

$2184$ $2200$

$2185$ $2200$

$2184$ $2199$

$1$ $100000$

Output:

1

0

0

13

explanation: [2184,2200] is a co-prime interval because it does not contain any other co-prime interval.

[2185,2200] is not a co-prime interval because 2197 is co-prime to all other numbers in that range.Same thing goes for [2184,2199] with 2189, so the answer to queries 2 and 3 is 0 (because again they don't contain any other co-prime interval).

The answer to the 4th query is 13 because there are 13 different co-prime intervals contained in the range [1,10^5].

I am looking for the optimal solution apart from the usual approach by trying every possible number in the range [A,B].

can someone help me with this.

thanks

Answer 1

This is an overlong comment (or might turn into a solution over time). At least it may give some hints to possible approaches.

Lemma 1. The length of a coprime interval is $\ge 5$.

Proof. If the length is $1$, the the only element is trivially co-prime to all others. If the length is $2$, the two elements are consecutive, hence coprime. If the length is $3$, the middle element is coprime to both its neighbours. If the length is $4$, there are exactly two odd elements, but at distance $2$ they cannot have an odd common divisor. One of them is not at the end of the interval, hence also coprime to the even members, its neighbours. $_\square$

Lemma 2. If $[a,b]$ is coprime, then all its members are composite.

Proof. Assume otherwise and let $p$ be the greatest prime in $[a,b]$ (apart from composites and priems, we also have $1$, but $1$ is coprime to everything). Then anotther multiple of $p$ must be in the interval, i.e. $b\ge 2p$. But by Bertrand's postulate, there exists a prime $q$ with $p<q\le 2p$, contradicting the maximality of $p$. $_\square$

Let $S_0$ be the set of primes, $\cup\{1\}$. Given $S_n$, let $S_{n+1}$ be $S_0$, enlarged by all numbers $m$ with the following property: Let $s=\max(S_n\cap\{1,\ldots,m-1\})$ and $t=\min(S_n\setminus\{1,\ldots,m\})$; then $m$ is added if $t-s\le 5$ or the smallest prime factor of $m$ is $\ge \max\{m-s,t-m\}$. Finally, let $S=\bigcup_n S_n$.

Lemma 3. If $[a,b]$ is coprime, then $[a,b]\cap S=\emptyset$.

Proof. It follows by induction that $[a,b]\cap S_n=\emptyset$ for all $n$: The case $n=0$ is lemma 2. If $[a,b]\cap S_n=\emptyset$, then for $m\in[a,b]$ with $s<m<t$, $s,t\in S_n$, we have $s<a\le m\le b<t$ and hence: if $t-s\le 5$ we arrive at a contradiction from lemma 1; and if all prime factors of $m$ are $\ge m-s$ and $\ge t-m$, then $m$ is coprime to all numbers in $[s+1,t-1]$, again a contradiciotn. we conclude ta also $S_{n+1}\cap[a,b]=\emptyset$. $_\square$

It is possible to enumerate the elements of $S$ by a computer program quite fast (for not too ambitious ranges) in ascending order. In turns out that the complement of $S$ is $$\tag1\mathbb N-S=[2184, 2200] \cup [27828, 27846] \cup [32214, 32230] \cup [57860, 57876] \cup [62244, 62260] \cup [87890, 87910] \cup [92274, 92290] \cup [110990, 111010] \cup [117920, 117936] \cup [122304, 122320] \cup\ldots $$ Within these relatively rare candidate intervals, it seems already promising to do a more or less brute-forvce search. (This search can still be quite fast if one does bookkeeping about the minimal prime factor of each number in the interval)

Here's a suggested algorithm to count the coprime intervals contained in $[A,B]$ where $[A,B]\cap S=\emptyset$ (i.e. is one of the intervals occurring in $(1)$ or a subinterval of such an interval):

1. Set $N\leftarrow 0$.
2. Set $a\leftarrow A$.
3. Set $b\leftarrow a$ and $m\leftarrow a$.
4. Let $p$ be the smallest prime divisor of $m$.
5. If $m-p<a$ and $m+p>b$ set $b\leftarrow m+p$. If this makes $b>B$, go to step 8.
6. If $m=b$ increase $N$ and $b$ by $1$.
7. Increase $m$ by $1$ and go to step 4.
8. Increase $a$ by one.
9. If $a>B-4$ terminate with $N$ as the asnwer. Othrewise go to step 3.

It may be worthwhile to cache the divisors computed in step 4. Also, I suspect that it is not less efficient to use only a simple approximation to $S$ auch as $[1,2183]\cup [2201,27827]\cup\{\text{primes}\}$