|
%I #15 May 17 2022 11:26:50
%S 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,
%T 164,1948,1467,2998,20561,66700,130236,153058,181635,239386,343189,
%U 1600832,5001577,16859525,45119463,66785667,218923884,393626778,665307164,3111228585,2156371427
%N Number of the essentially different permutations of the numbers 0 to n such that the sum of adjacent numbers is a square.
%C 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.
%e n=14: one solution
%e {8,1,0,9,7,2,14,11,5,4,12,13,3,6,10};
%e n=15: three solutions
%e {0,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8},
%e {5,11,14,2,7,9,0,4,12,13,3,6,10,15,1,8},
%e {8,1,0,9,7,2,14,11,5,4,12,13,3,6,10,15};
%e n=16: four solutions
%e {0,16,9,7,2,14,11,5,4,12,13,3,6,10,15,1,8},
%e {5,11,14,2,7,9,16,0,4,12,13,3,6,10,15,1,8},
%e {8,1,0,16,9,7,2,14,11,5,4,12,13,3,6,10,15},
%e {8,1,15,10,6,3,13,12,4,5,11,14,2,7,9,0,16}.
%t 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}]
%Y Cf. A071984, A090460, A108659, A108660, A108661.
%K hard,nice,nonn
%O 0,16
%A _Zak Seidov_, _T. D. Noe_ & _Max Alekseyev_, Jun 16 2005
%E a(42)-a(50) from _Bert Dobbelaere_, Dec 30 2018
|
