I've been working on the following problem for a while:
Prove that it's possible to arrange numbers 1 to 1000 an order such that each number appears once and |$x_j – x_{j+1}$| is not a perfect square nor a prime number.
The idea is just to prove that such an ordering exists, not to explicitly construct it (thankfully).
My first thought was to try to construct an explicit ordering of 1 to 10 that satisfies the given constraints and then see if I could extrapolate a pattern. Unfortunately, I wasn't able to do this (5 minus any other number in that sequence gives either a prime or a perfect square, I believe…)
I found online that there are 168 primes and 31 perfect squares between 1 and 1000, and this seems like potentially useful information. However, I'm still not able to connect the dots and figure out how to think about this problem … Any help would be much appreciated.
Best Answer
Consider the graph with 1000 vertices where vertex $i$ is adjacent to $j$ iff $|i-j|$ is neither prime nor square.
There are at most $2*(168+31)=398$ vertices which are not adjacent to any point, so each vertex has degree at least $999-398=601>1000/2$. Since each vertex has degree greater than half the size of the graph, it's a well-known theorem that there is a Hamiltonian circuit. Use that ordering. Thus, you can arrange the numbers from 1 to 1000 so that no two consecutive ones have a difference which is a prime or a square.