# Nice Puzzle

#### Amer

##### Active member
Arrange the numbers: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
such that the summation of each two successive numbers is a complete square easy interesting question

#### MarkFL

Staff member
8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9

#### Bacterius

##### Well-known member
MHB Math Helper
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.

#### chisigma

##### Well-known member
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.
If n=2 k + 1 is a perfect square and the set is 1,2,..., 2k then is...

2 K + 1 = 2k-1 + 2 = 2 k -2 + 3 + ... = k+1 + k = n (1)

Of course however that is a very particular case...

Kind regards

$\chi$ $\sigma$

#### Barioth

##### Member
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!

#### Bacterius

##### Well-known member
MHB Math Helper
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!
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.

#### Bacterius

##### Well-known member
MHB Math Helper
Actually my bad, I wrote the above in a hurry. n = 16 actually has solutions, namely:

(8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16)
(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8)

n = 17 has the following solutions:

(17, 8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16)
(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, 17)

n = 18 to n = 22 have no solutions.

n = 23 has the following solutions:

(22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 14, 11, 5, 20, 16, 9, 7, 18)
(18, 7, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9)
(2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22, 14, 11, 5, 20, 16, 9, 7, 18)
(9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2, 7, 18)
(18, 7, 9, 16, 20, 5, 11, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22)
(18, 7, 9, 16, 20, 5, 11, 14, 22, 3, 1, 8, 17, 19, 6, 10, 15, 21, 4, 12, 13, 23, 2)

There will always be an even number of solutions, obviously.

Looks mysterious ...

An observation is that for n close to 15, the solutions tend to reuse the existing solution for n = 15 in some way (here 16 is added at the end, and after that 17 is added at the beginning), which I guess makes sense heuristically. The pattern breaks down for n = 23 though, there are bits of the original solution e.g. (8, 1, 15) but overall it changes quite a bit.

This is actually an interesting and deep problem. I wonder if it's NP-complete (probably not, if we limit ourselves to inputs of the form {1, 2, 3, ..., n} there should be an efficient way to find solutions. wouldn't surprise me if the full generalization is NP-complete though)

Last edited:

#### Amer

##### Active member
if we have three numbers in the given set that just has one mate from the set ( i mean by the mate, the summation of the two mates is a complete square ) then we cant order them

in our set 1,2,3,...,15
we have two such numbers which will be at the ends of the arrangement 9,8

for example 1,2,3,4,...,10
we cant order it since 10,9,8 has one mate