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

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.

• That it is always solvable can be seen by considering all integers between $A$ and $B$ ( $N_1=A+1$, $N_2=A+2$,..). This shows $L \leq B-A-1$. – polkjh May 1 '13 at 16:21
• polkjh: that seems to work, given that GCD( n, n+1 ) = 1 (which is true). – DarthShader May 1 '13 at 16:42
• Please use the latex support available on this site. – Aryabhata May 2 '13 at 15:28
• – Aryabhata May 2 '13 at 16:56
• I think you may have more luck on Mathematics. – Kaveh Jan 3 '16 at 9:45

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