|
| |
|
|
A090460
|
|
Number of essentially different permutations of the numbers 1 to n such that the sum of adjacent numbers is a square.
|
|
10
|
|
|
|
1, 1, 1, 0, 0, 0, 0, 0, 3, 0, 10, 12, 35, 52, 19, 20, 349, 361, 637, 3678, 15237, 11875, 13306, 10964, 27223, 37054, 201408, 510152, 1995949, 4867214, 11255174, 35705858, 63029611, 129860749, 258247089, 190294696, 686125836, 2195910738, 5114909395, 9141343219, 19769529758, 44678128099, 63885400119
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
15,9
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
EXAMPLE
|
|
|
|
MATHEMATICA
|
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
|
|
|
CROSSREFS
|
Cf. A078107 (n for which there is no solution).
|
|
|
KEYWORD
|
hard,nonn,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
