|
Search: id:A090460
|
|
|
| A090460 |
|
Number of essentially different permutations of the numbers 1 to n such that the sum of adjacent numbers is a square. |
|
+0
8
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
15,9
|
|
|
COMMENT
|
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.
|
|
FORMULA
|
a(n) = A071983(n) - (n-1)*A071984(n)
|
|
EXAMPLE
|
See A071983
|
|
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. A071983, A071984 (number of circular solutions), A090461 (n for which there is a solution).
Cf. A078107 (n for which there is no solution).
Sequence in context: A119957 A028852 A095200 this_sequence A071983 A094897 A019264
Adjacent sequences: A090457 A090458 A090459 this_sequence A090461 A090462 A090463
|
|
KEYWORD
|
hard,nonn
|
|
AUTHOR
|
T. D. Noe (noe(AT)sspectra.com), Dec 01 2003
|
|
|
Search completed in 0.004 seconds
|
