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,16

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.

Links

Table of n, a(n) for n=0..50.

Example

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}.

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]]<soln[[n+1]])||(circular&&soln[[1]]\[Equal]1&&soln[[2]]\[LessEqual]soln[[n+1]]), Print[soln]; (**)cnt++ ], (*else append another number to the soln list*)t=soln[[lev-1]]; For[j=1, j\[LessEqual]Length[s[[t+1]]], j++, If[ !MemberQ[soln, s[[t+1]][[j]]], soln[[lev]]=s[[t+1]][[j]]; try[lev+1]; soln[[lev]]=-1]]]]; nMax=30; Table[s=Table[{}, {n+1}]; Do[If[i\[NotEqual]j&&SquareQ[i+j], AppendTo[s[[i+1]], j]], {i, 0, n}, {j, 0, n}]; soln=Table[ -1, {n+1}]; cnt=0; Do[soln[[1]]=i; try[2], {i, 0, n}]; cnt, {n, 0, nMax}]

Crossrefs

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

Sequence in context: A287986 A190959 A038018 * A240669 A213201 A245843

Adjacent sequences: A108655 A108656 A108657 * A108659 A108660 A108661

Keyword

hard,nice,nonn

Author

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

Extensions

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

Status

approved