A puzzle on gcd

Question

Consider a directed graph whose nodes are positive integers. There is a directed edge from $a$ to $b$ if $a<b$ and $a$ is relatively prime to $b$, i.e. $\mathrm{gcd}(a,b)=1$. Given two integers $x,y$ with $x<y$, $d(x,y)$ is the number of edges in the shortest path from $x$ to $y$. What is the largest value of $d(x,y)$?

I suspect the answer is 3, but I don't have a proof.

via Puzzle Tweeter

Answer 1

Here are some thoughts which do not fit into the 600 symbols of a comment:

• If $y \geq 2x$, then $d(x,y) \leq 2$.

Proof: For $y \leq 7$, this is easily checked. Otherwise by Bertrand's postulate, there is a prime $p$ with $x \leq \lceil y/2\rceil < p < y$. Now $\gcd(x,p) = \gcd(p,y) = 1$, so $d(x,y) \leq 2$.

• If there is a prime in the range $\{x,\ldots,y\}$, then $d(x,y) \leq 2$.

By the last statement, we may assume $y < 2x$. Let $p$ be prime with $x \leq p \leq y$. Then $\gcd(x,p) = 1$, and because of $y < 2p$ also $\gcd(p,y) = 1$.

I used this property for a computer search for pairs $(x,y)$ with $d(x,y) > 2$. They turn out to be quite rare. The smallest ones are

  2184   2200
 27830  27846
 32214  32230
 57860  57876
 62244  62260
 87890  87906
 92274  92290
117920 117936
122304 122320
147950 147966
152334 152350
177980 177996
182364 182380
208010 208026
212394 212410
238040 238056
242424 242440
268070 268086
272454 272470
298100 298116
302484 302500
328130 328146
332514 332530
358160 358176
362544 362560
388190 388206
392574 392590
418220 418236
422604 422620
448250 448266
452634 452650
478280 478296
482664 482680

In each such pair, $d(x,y) = 3$ and interestingly $y - x = 16$.