7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ related: stackoverflow.com/questions/16352543 $\endgroup$ – azimut Aug 30 '13 at 0:02
  • $\begingroup$ Where did you find this question? $\endgroup$ – azimut Aug 30 '13 at 0:14
  • $\begingroup$ 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. $\endgroup$ – Gowtham Aug 30 '13 at 0:28
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – D. Thomine Aug 30 '13 at 0:27
  • $\begingroup$ @D.Thomine: Right, thanks for your comment! I really should have recognized the periodicity by $30030$. $\endgroup$ – azimut Aug 30 '13 at 0:37
  • 1
    $\begingroup$ @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$. $\endgroup$ – Daniel Fischer Aug 30 '13 at 1:04
  • $\begingroup$ 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. $\endgroup$ – D. Thomine Aug 30 '13 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.