Arrange the numbers 1 to 15 inclusively in a straight line in such a way that any two adjacent numbers add up to a perfect square.

Suppose we are instead asked to arrange 1 to n instead.

(1) Show that this is not possible if 1<n<15.

(2) Show that there are solutions for n=16 and n=17.

(3) Find the next value of n>17 for which there is a solution.