Problem 633. Create Circular Perfect Square Sequence

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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&lt;N&lt;52 as solutions beyond 51 may take significant processing time.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

27 Solutions
9 Solvers

Last Solution submitted on Sep 19, 2022

Last 200 Solutions

Problem Comments

7 Comments

7 Comments

Show 4 older comments

@bmtran (Bryant Tran) on 30 Apr 2012

you might want to specify in the problem that the sequence has to be made of N unique values

@bmtran (Bryant Tran) on 30 Apr 2012

sorry, my mistake; it was unclear to me at first that the sequence had to contain a permutation of the values 1:N

Richard Zapor on 30 Apr 2012

Thank You. I have clarified that each value must be used.

@bmtran (Bryant Tran) on 30 Apr 2012

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)

Alfonso Nieto-Castanon on 29 Dec 2012

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

Jean-Marie Sainthillier on 29 Sep 2014

Hello Richard, Hello Alfonso, Hello @bmtran, Is it possible to solve this kind of problem without recursion ?

Alfonso Nieto-Castanon on 30 Sep 2014

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?)

Solution Comments

Show comments

Problem Recent Solvers9

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 633. Create Circular Perfect Square Sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers9

Suggested Problems

More from this Author294

Problem Tags

Community Treasure Hunt

Problem 633. Create Circular Perfect Square Sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers9

Suggested Problems

More from this Author294

Problem Tags

Community Treasure Hunt

Players