Un rompecabezas en mcd

Question

Considere un grafo dirigido cuyos nodos son enteros positivos. Hay un borde dirigido de $a$ $b$si $a<b$ $a$ es relativamente primer a $b$, es decir,$\mathrm{gcd}(a,b)=1$. Dados dos enteros $x,y$ con $x<y$, $d(x,y)$ es el número de aristas en el camino más corto de$x$$y$. ¿Cuál es el mayor valor de $d(x,y)$?

Sospecho que la respuesta es 3, pero no tengo una prueba.

a través de Rompecabezas de Tweeter

Answer 1

Aquí están algunas ideas que no encajan en el 600 símbolos de un comentario:

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

Prueba: Por $y \leq 7$, esto es fácilmente controlado. De lo contrario, por el postulado de Bertrand, hay un primer $p$$x \leq \lceil y/2\rceil < p < y$. Ahora $\gcd(x,p) = \gcd(p,y) = 1$, lo $d(x,y) \leq 2$.

• Si hay un prime en el rango de $\{x,\ldots,y\}$,$d(x,y) \leq 2$.

Por la última instrucción, podemos suponer que $y < 2x$. Deje $p$ principales con el $x \leq p \leq y$. A continuación,$\gcd(x,p) = 1$, y debido a $y < 2p$$\gcd(p,y) = 1$.

He utilizado esta propiedad para un equipo de búsqueda de los pares de $(x,y)$$d(x,y) > 2$. Resultan ser bastante raro. Los más pequeños son

  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

En cada par, $d(x,y) = 3$ y curiosamente $y - x = 16$.