If n=2 k + 1 is a perfect square and the set is 1,2,..., 2k then is...I can think of a backtracking algorithm to solve this relatively efficiently given any input set. Might code it up tomorrow. Does anyone have a way to attack this analytically (again, for any input set, not just consecutive integers, and return any solution sequence - or none if there are none). An argument for the associated decision problem would be interesting to see too.
There are actually two solutions for n = 15, forward and reverse (obviously). There are no others. Solutions are not guaranteed to exist. There are none for n = 16, for instance (checked myself). Curiously there apparently are solutions for n = 30 and n = 60 (unsure, I'll check later). I have been working on two versions of an algorithm but they always end up having exponential complexity, because I can't find a good algorithm. I might post my drafts once I come back from comp labs.I solved it too using
a matrix (I named my matrix A) with \(\displaystyle A_ab=1 if a+b=perfect square\)
It's pretty much done once you have the matrix, you see that 8 as the be the first (or last) number.
I ended with the same solution as MarkFL, and I was wondering if there is always a solution for n large enough?
and if that solution(if it exist) was unique?
I know that for this case with n =15 the solution is unique.
I'll take a look at it tomorow (right now I need to hit the bed) if someone find something before I do let me know!