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.
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<52 (0.84s median time), yet it would choke for the particular value N=42 (past the end of my patience as well)...
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 heuristic-search algorithms without explicitly using recursion, or you could use non-search-based approaches, such as annealing, integer linear programming, etc. Now if you are asking whether exhaustive or other polynomial-time 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 N-node graph, so the only hope of bringing this out of the NP-hard 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?)
a bit faster (median t=0.56s for 31<52 on my machine)