The length of the smallest co-prime chain between any two integers Consider the following statement:

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

$\gcd(a,b) = 1$.
there is a $a &lt; x &lt; b$ such that
$\gcd(a,x) = \gcd(x,b) = 1$.
there are $a &lt; x &lt; y &lt; 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 &lt; x_1 &lt; x_2 &lt; \ldots &lt; x_l &lt; 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:

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

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

$a = 2184, b = 2200$:
There is no $a&lt; x &lt; 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

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

$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.
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 &gt; 1$ then $b-a$ is an Erdős-Woods number. In particular, if $\ell &gt; 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 &gt; 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$.