Consider a directed graph whose nodes are positive integers. There is an edge from a to b if a<b and a is relatively prime to b. 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)?

- via a friend at Packard

The answer should be the largest prime gap known. Between any two x,y if both x and y are prime d(x,y) = 1. If there exists a prime number between them(say p), and gcd(p,y) = 1 then there is an edge from p to y and the count gets reduced. If gcd(p,y)!=1, then we need to traverse all edges from x to y. Example d(7,10) = 3 since there are no prime numbers but d(5,10) = 2 (5->7->10). @Admin: Hints if this is wrong.

d(7,10) = 1. Ignore the above reasoning. It is wrong.

There are a few problems that I don't know the answer to, and this is one of them.

Pingback: A puzzle on gcd - MathHub