Gaby's Puzzle (Primes Around a Circle)

Question

To keep them busy during lockdown, Gaby asked her children to find a way to place the first sixteen primes (2 to 53) around a circle so that either the sum or difference (or both) of any two of them which were adjacent was a perfect square.

They all found entirely different solutions (i.e. not merely rotations or reflections of each other's solutions) and, in fact, all of their solutions were different from their mother's own solution. Moreover, when she checked, no other solutions would have been possible.

How many children does Gaby have?

Answer 1

The full list of possibilities that each prime can be adjacent to is as follows:

2: $3,7,11,23,47$
3: $2,7,13,19$
5: $11,31,41$
7: $2,3,11,23,29,43$
11: $2,5,7,47,53$
13: $3,17,23,29$
17: $13,19,47,53$
19: $3,17,23$
23: $2,7,13,19,41$
29: $7,13$
31: $5,47$
37: $41,53$
41: $5,23,37$
43: $7,47$
47: $2,11,17,31,43,53$
53: $11,17,37,47$

The key ones to notice are

$29,31,37,43$, each of which has only two others it can be adjacent to. Three of these even join up to each other, so we get a string of adjacent numbers $13,29,7,43,47,31,5$.

Now there are only two possibilities for the other number next to $5$, namely $11$ or $41$.

If it's $41$, then next to that must be $37$ and then $53$, while now $11$ can only be adjacent to $2$ and $53$. Now there's only four numbers remaining (between $13$ and $2$ on the circle), namely $3,17,19,23$. Considering the list that $17$ can be adjacent to, we see that next to $13$ must be $17$ and then $19$, leaving $3$ and $23$ adjacent, contradiction.

So it must be $11$ next to $5$, then next to that must be either $2$ or $53$.

1. If it's $53$, then next to that must be $37$ and then $41$ and then $23$, leaving only four numbers ($2,3,17,19$) left to place between $13$ and $23$ on the circle. Looking at the options for $17$, we see that next to $13$ must be $17$ and then $19$, then $3$ and finally $2$ next to $23$.

2. If it's $2$ next to $11$, then we know the string $23,41,37,53,17$ (in either direction) but not where to place it. Apart from that string of length five, only $3$ and $19$ are left to place, all seven numbers somewhere between $13$ and $2$ on the circle. Now $19$ can't be next to either $13$ or $2$, so either we start next to $13$ and place $3$ then $19$ then $17,53,37,41,23$, or we start next to $2$ and place $3$ then $19$ then the string of length five in either possible order.

So altogether we have

four possibilities, which means Gaby has three children.

I've tried to illustrate this as follows: