Problem 633. Create Circular Perfect Square Sequence

Created by Richard Zapor

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.

Problem Group

Community

Solve This Now!

3 solvers submitted 15 solutions (5.0 solutions/solver).

Solution Map Solution List Solvers

Problem Comments

1 player likes this problem

5 Comments

Show 2 older comments

@bmtran on 30 Apr 2012

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

@bmtran 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 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<N<52 (0.84s median time), yet it would choke for the particular value N=42 (past the end of my patience as well)...

Problem 633. Create Circular Perfect Square Sequence

Tags

Problem Group

3 solvers submitted 15 solutions (5.0 solutions/solver).

Problem Comments

Solution Comments