Arranging numbers 1 to 1000 such that the difference of two adjacent numbers is not a square nor a prime number 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.
 A: 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.
A: You can also construct it:
Start with $1$ and keep adding $6$ i.e $1,7,13$ until you hit $997$ then go back to $3$ and keep adding $6$ until you get to $999$ and go back to $5$ repeat until $995$ then go back to $2$ repeat until $998$ and go back to $4$ repeat until $1000$ and go back to $6$ repeat until $996$ and you're finished.
The difference between consecutive terms is either $6,994,993$ - those clearly aren't primes, and $993$ and $994$ aren't perfect squares since they are $>31^2$ (and $32^2>1000$).
