|
%I #39 May 01 2024 03:06:33
%S 1,1,1,0,0,0,0,0,3,0,10,12,35,52,19,20,349,361,637,3678,15237,11875,
%T 13306,10964,27223,37054,201408,510152,1995949,4867214,11255174,
%U 35705858,63029611,129860749,258247089,190294696,686125836,2195910738,5114909395,9141343219,19769529758,44678128099,63885400119
%N Number of essentially different permutations of the numbers 1 to n such that the sum of adjacent numbers is a square.
%C 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.
%H Zhao Hui Du, <a href="/A090460/b090460.txt">Table of n, a(n) for n = 15..59</a>
%F a(n) = A071983(n) - (n-1)*A071984(n).
%e See A071983.
%t 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 Cf. A071983, A071984 (number of circular solutions), A090461 (n for which there is a solution).
%Y Cf. A078107 (n for which there is no solution).
%K hard,nonn
%O 15,9
%A _T. D. Noe_, Dec 01 2003
%E a(43)-a(45) from _Donovan Johnson_, Sep 14 2010
%E a(46)-a(47) from _Jud McCranie_, Aug 18 2018
%E a(48) from _Jud McCranie_, Sep 17 2018
%E a(49)-a(52) from _Bert Dobbelaere_, Dec 30 2018
%E a(47) corrected by _Bert Dobbelaere_, Jan 12 2019
%E a(53)-a(54) from _Martin Ehrenstein_, May 22 2023
%E a(55)-a(57) from _Zhao Hui Du_, Apr 26 2024
|
