4
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oh yeah, I hadn't even thought about Hamiltonian circuits. Thanks so much for this clear explanation. $\endgroup$ – nero Apr 18 at 5:00
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Slightly less obvious but simpler to describe the construction: just add $91$ each time (or subtract $909$ on wraparound). $\endgroup$ – Erick Wong Apr 18 at 9:07
  • 1
    $\begingroup$ @ErickWang Yeah that's easier to describe , $77$ as well (though it's harder to prove that $923$ is composite), the wraparound is constant because $91\mid 1001$ and $77\mid 1001$ (you probably know this but might be useful for the OP). $\endgroup$ – kingW3 Apr 18 at 9:35

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.