# A puzzle on gcd

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.

• – azimut Aug 30 '13 at 0:02
• Where did you find this question? – azimut Aug 30 '13 at 0:14
• I was talking to a friend who attempts top-coder programming. This is a 1000-point problem (the hardest). You are asked to compute and print d(x,y). All the people who solved it assumed that the largest d(x,y) is 3, so all they did was check if $d(x,y)\le 2$. It seemed simple to prove, but it turns out to be harder. I like your insight using Bertrand's paradox. – Gowtham Aug 30 '13 at 0:28

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

• It is not surprinsing that $y-x = 16$ for all your examples. There is essentially only one pattern, which is due to a particular configuration of the residue classes modulo 2, 3, 5, 7, 11 and 13 (every larger prime only occurs once in an interval of length 16, so has no influence on the graph between the two extremities). Since 2*3*5*7*11*13 = 30030, you get another pair by adding 30030 to both extremities. Exchange the residues of the beginning and the end to get a second sequence of period 30030, and you get all your examples. – D. Thomine Aug 30 '13 at 0:27
• @D.Thomine: Right, thanks for your comment! I really should have recognized the periodicity by $30030$. – azimut Aug 30 '13 at 0:37
• @Gowtham It's only a counterexample to the conjecture that one can always choose $(a+1,b-1)$ as the two numbers to insert. There are a lot of pairs you can insert so that all GCDs of the neighbours are $1$. – Daniel Fischer Aug 30 '13 at 1:04
• Another thought: the problem with brute-force search is that the problem looks like a combinatorial problem with primes, and that more primes may be needed to get larger distances. It may be possible that we can find chains of length $n$ for any $n$, but only by looking at numbers of the order of the factorial prime of $n$ - unreachable by blind testing pairs of integers. – D. Thomine Aug 30 '13 at 19:13