Log In

Largest gcd distance

Posted on: August 29th, 2013 by

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

4 Responses to Largest gcd distance

  1. Shaleen had this to say about that:

    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.

  2. Pingback: A puzzle on gcd - MathHub

{"result":"error", "message":"You can't access this resource as it requires an 'view' access for the website id = 1."}