The length of the smallest co-prime chain between any two integers

Question

Consider the following statement:

for any $a < b \in \mathbb{N}$, one of the following holds:

1. $\gcd(a,b) = 1$.
2. there is a $a < x < b$ such that $\gcd(a,x) = \gcd(x,b) = 1$.
3. there are $a < x < y < b$ such that $\gcd(a,x) = \gcd(x,y) = \gcd(y,b) = 1$.

Is this statement true?

---

Motivation:

I found a variant of this problem in one of the recent algorithms competitions.

Consider the following problem:

Input: two integers $a$ and $b$ where $a \lt b$.

Output: smallest number $l$ such that there are integers $a = x_0 < x_1 < x_2 < \ldots < x_l < x_{l+1} = b$ such that all consecutive integers in the list are co-prime: $\gcd(x_i, x_{i+1}) = 1$ for $i=0,\ldots, l$.

Examples:

1. $a = 7, b = 13$: $\gcd(a,b) = 1$, therefore $l = 0$.

2. $a = 10, b = 12$: $\gcd(a,b) = 2 \neq 1$, therefore $l \geq 1$. Let the sequence be $10, 11, 12$. $\gcd(10, 11) = 1, \gcd(11, 12) = 1$.

3. $a = 2184, b = 2200$: There is no $a< x < b$ such that $\gcd(a,x)=\gcd(x,b)=1$. However, we can find $2$ integers that satisfy this problem.

There is a reference algorithm that algorithms are evaluated against. That algorithm assumes that

1. There is always an $l$ that satisfies the condition.

2. $l\leq 2$.

I don't see why they are true.

I have a polynomial time algorithm that does not assume either of them. I am not losing out on the asymptotic performance compared to the reference algorithm, but I could get the performance constants much lower if I can understand and prove the validity of the assumptions.

Answer 1

The conjecture $\ell \leq 2$ seems to be open. It is stated as Conjecture 3 in a paper of Dowe. Dowe does show that the Goldbach conjecture implies that $\ell \leq 3$, and mentions that Alan Woods showed in his PhD thesis that $\ell$ is bounded. Perhaps the recent proof of the odd Goldbach conjecture also implies a definite and small bound.

If $\ell > 1$ then $b-a$ is an Erdős-Woods number. In particular, if $\ell > 2$ then both $b-a$ and $b-a-1$ have to be Erdős-Woods numbers. A059756 lists the first few Erdős-Woods numbers. While all numbers on that list are even, there are also odd Erdős-Woods numbers, some of which are listed in A111042. The smallest values of $a$ corresponding to given differences are listed in A059757. While this list is not increasing, it does seem as if the numbers are growing pretty fast. Any counterexample to $\ell \leq 2$ would to be such that both $b-a$ and $b-a-1$ are Erdős-Woods numbers, and in particular $b-a > 430$ (per A059756). This suggests (but does not prove) that any such counterexample will be huge, and so for all practical purposes we can assume that $\ell \leq 2$.