A108658 Number of the essentially different permutations of the numbers 0 to n such that the sum of adjacent numbers is a square.

1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 4, 4, 0, 0, 4, 5, 2, 8, 7, 47, 72, 135, 283, 158, 164, 1948, 1467, 2998, 20561, 66700, 130236, 153058, 181635, 239386, 343189, 1600832, 5001577, 16859525, 45119463, 66785667, 218923884, 393626778, 665307164, 3111228585, 2156371427

Offset: 0

Author

Zak Seidov, T. D. Noe & Max Alekseyev, Jun 16 2005

Keywords

• hard
• nice
• nonn

Comments

Square chains (reversals not counted and circles counted once). There is no solution for n=2-13,18-19 (note offset=0). For n=0 and n=1 we have trivial square circles (which are also known as square loops). Square circles seem to appear for all n>30, see A108661. Cf. A090460 for 1-to-n case.

Examples

			n=14: one solution
  {8,1,0,9,7,2,14,11,5,4,12,13,3,6,10};
n=15: three solutions
  {0,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8},
  {5,11,14,2,7,9,0,4,12,13,3,6,10,15,1,8},
  {8,1,0,9,7,2,14,11,5,4,12,13,3,6,10,15};
n=16: four solutions
  {0,16,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8},
  {5,11,14,2,7,9,16,0,4,12,13,3,6,10,15,1,8},
  {8,1,0,16,9,7,2,14,11,5,4,12,13,3,6,10,15},
  {8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,0,16}.
		

Crossrefs

Cf. A071984, A090460, A108659, A108660, A108661.

Programs

Mathematica

SquareQ[n_]:=IntegerQ[Sqrt[n]]; try[lev_]:=Module[{t, j, circular}, If[lev>n+1, circular=SquareQ[soln[[1]]+soln[[n+1]]]; If[(!circular&&soln[[1]]
				

Extensions

a(42)-a(50) from Bert Dobbelaere, Dec 30 2018