Ordenar los números del 1 al 1000 de forma que la diferencia de dos números adyacentes no sea un cuadrado ni un número primo

Question

Llevo un tiempo trabajando en el siguiente problema: Demostrar que es posible organizar los números del 1 al 1000 en un orden tal que cada número aparezca una vez y | $x_j - x_{j+1}$ | no es un cuadrado perfecto ni un número primo.

La idea es sólo demostrar que ese ordenamiento existe, no construirlo explícitamente (afortunadamente).

Lo primero que pensé fue en intentar construir una ordenación explícita del 1 al 10 que satisficiera las restricciones dadas y luego ver si podía extrapolar un patrón. Lamentablemente, no pude hacerlo (5 menos cualquier otro número de esa secuencia da un primo o un cuadrado perfecto, creo...)

He encontrado en Internet que hay 168 primos y 31 cuadrados perfectos entre 1 y 1000, y esto parece una información potencialmente útil. Sin embargo, todavía no soy capaz de conectar los puntos y averiguar cómo pensar en este problema ... Cualquier ayuda sería muy apreciada.

Answer 1

Consideremos el grafo con 1000 vértices donde el vértice $i$ es adyacente a $j$ si $|i-j|$ no es ni primo ni cuadrado.

Hay como máximo $2*(168+31)=398$ vértices que no son adyacentes a ningún punto, por lo que cada vértice tiene grado al menos $999-398=601>1000/2$ . Como cada vértice tiene un grado mayor que la mitad del tamaño del gráfico, es un teorema bien conocido que existe un circuito hamiltoniano. Utiliza esa ordenación. Así, se pueden ordenar los números del 1 al 1000 de forma que ninguno de los dos consecutivos tenga una diferencia que sea un primo o un cuadrado.

Answer 2

También puedes construirlo:
Comience con $1$ y seguir añadiendo $6$ es decir $1,7,13$ hasta que se golpea $997$ y luego volver a $3$ y seguir añadiendo $6$ hasta llegar a $999$ y volver a $5$ repetir hasta que $995$ y luego volver a $2$ repetir hasta que $998$ y volver a $4$ repetir hasta que $1000$ y volver a $6$ repetir hasta que $996$ y has terminado.

La diferencia entre términos consecutivos es $6,994,993$ - esos claramente no son primos, y $993$ y $994$ no son cuadrados perfectos ya que son $>31^2$ (y $32^2>1000$ ).