%I A090460
%S A090460 1,1,1,0,0,0,0,0,3,0,10,12,35,52,19,20,349,361,637,3678,15237,11875,
%T A090460 13306,10964,27223,37054,201408,510152
%N A090460 Number of essentially different permutations of the numbers 1 to n such 
               that the sum of adjacent numbers is a square.
%C A090460 For n > 31, some solutions are circular; that is, the first and last 
               numbers also sum to a square. Note that A071983 counts each circular 
               solution n times. This sequence counts each circular solution only 
               once. The Mathematica program uses backtracking to find all solutions, 
               which can be printed by removing the comment symbols.
%F A090460 a(n) = A071983(n) - (n-1)*A071984(n)
%e A090460 See A071983
%t A090460 SquareQ[n_] := IntegerQ[Sqrt[n]]; try[lev_] := Module[{t, j, circular}, 
               If[lev>n, circular=SquareQ[soln[[1]]+soln[[n]]]; If[(!circular&&soln[[1]]<soln[[n]]) 
               || (circular&&soln[[1]]==1&&soln[[2]]<=soln[[n]]), (*Print[soln];
               *) cnt++ ], (*else append another number to the soln list*) t=soln[[lev-1]]; 
               For[j=1, j<=Length[s[[t]]], j++, If[ !MemberQ[soln, s[[t]][[j]]], 
               soln[[lev]]=s[[t]][[j]]; try[lev+1]; soln[[lev]]=0]]]]; nMax=32; 
               For[lst={}; n=15, n<=nMax, n++, s=Table[{}, {n}]; For[i=1, i<=n, 
               i++, For[j=1, j<=n, j++, If[i != j && SquareQ[i+j], AppendTo[s[[i]], 
               j]]]]; soln=Table[0, {n}]; For[cnt=0; i=1, i<=n, i++, soln[[1]]=i; 
               try[2]]; AppendTo[lst, cnt]]; lst
%Y A090460 Cf. A071983, A071984 (number of circular solutions), A090461 (n for which 
               there is a solution).
%Y A090460 Cf. A078107 (n for which there is no solution).
%Y A090460 Sequence in context: A119957 A028852 A095200 this_sequence A071983 A094897 
               A019264
%Y A090460 Adjacent sequences: A090457 A090458 A090459 this_sequence A090461 A090462 
               A090463
%K A090460 hard,nonn
%O A090460 15,9
%A A090460 T. D. Noe (noe(AT)sspectra.com), Dec 01 2003