Problem 633. Create Circular Perfect Square Sequence
A sequence v(1:N) made of values 1:N can be created for N>31 such that v(i)+v(i+1) is a perfect square. The sum of v(N)+v(1) must also be a perfect square. All values 1 thru N are required and the vector must be of length N. (e.g. For N=32 the possible perfect squares are [4 9 16 25 36 49]. By inspection the value 32 must be bracketed by 4 and 17). The Test set will be limited to 31<N<52 as solutions beyond 51 may take significant processing time.
Solution Stats
Problem Comments

7 Comments
you might want to specify in the problem that the sequence has to be made of N unique values
sorry, my mistake; it was unclear to me at first that the sequence had to contain a permutation of the values 1:N
Thank You. I have clarified that each value must be used.
oh man, this problem is brutal. i have a solution that can solve it for values of N between 33 and 39 inclusive in under a second, but as soon as I try 40 or 41, it runs forever (or at least past the end of my patience)
It seems there is a lot of variability depending on your particular search heuristics and the particular value of N. My solution performs in under 30 seconds for 19 out of the 20 cases 31
Hello Richard, Hello Alfonso, Hello @bmtran, Is it possible to solve this kind of problem without recursion ?
In general, sure, you can easily write these sort of heuristicsearch algorithms without explicitly using recursion, or you could use nonsearchbased approaches, such as annealing, integer linear programming, etc. Now if you are asking whether exhaustive or other polynomialtime approaches are possible/practical for this problem I am not really sure about that. I believe this problem reduces to finding a full hamiltonian cycle over an Nnode graph, so the only hope of bringing this out of the NPhard umbrella would be exploiting some properties of these particular networks arising from the properties of perfect numbers, but so far I do not see any useful trick in this regard (so in short, perhaps it is possible but I do not know how; any thoughts?)
Solution Comments
Show commentsProblem Recent Solvers9
Suggested Problems

2241 Solvers

Make an awesome ramp for a tiny motorcycle stuntman
621 Solvers

271 Solvers

5306 Solvers

Is this triangle rightangled?
5560 Solvers
More from this Author296
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!