login
A242529
Number of cyclic arrangements (up to direction) of numbers 1,2,...,n such that any two neighbors are coprime.
16
1, 1, 1, 1, 6, 2, 36, 36, 360, 288, 11016, 3888, 238464, 200448, 3176496, 4257792, 402573312, 139511808, 18240768000, 11813990400, 440506183680, 532754620416, 96429560832000, 32681097216000, 5244692024217600, 6107246661427200, 490508471914905600, 468867166554931200, 134183696369843404800
OFFSET
1,5
COMMENTS
a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S={1,2,...,n} of n elements and a specific pair-property P of "being coprime". For more details, see the link and A242519.
FORMULA
For n>2, a(n) = A086595(n)/2.
EXAMPLE
There are 6 such cycles of length n=5: C_1={1,2,3,4,5}, C_2={1,2,3,5,4},
C_3={1,2,5,3,4}, C_4={1,2,5,4,3}, C_5={1,3,2,5,4}, and C_6={1,4,3,2,5}.
For length n=6, the count drops to just 2:
C_1={1,2,3,4,5,6}, C_2={1,4,3,2,5,6}.
MATHEMATICA
A242529[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[cpf[x], # != 1 &]];
cpf[x_] := Module[{i},
Table[GCD[x[[i]], x[[i + 1]]], {i, Length[x] - 1}]];
Join[{1, 1}, Table[A242529[n], {n, 3, 10}]]
(* OR, a less simple, but more efficient implementation. *)
A242529[n_, perm_, remain_] := Module[{opt, lr, i, new},
If[remain == {},
If[GCD[First[perm], Last[perm]] == 1, ct++];
Return[ct],
opt = remain; lr = Length[remain];
For[i = 1, i <= lr, i++,
new = First[opt]; opt = Rest[opt];
If[GCD[Last[perm], new] != 1, Continue[]];
A242529[n, Join[perm, {new}],
Complement[Range[2, n], perm, {new}]];
];
Return[ct];
];
];
Join[{1, 1}, Table[ct = 0; A242529[n, {1}, Range[2, n]]/2, {n, 3, 12}] ](* Robert Price, Oct 25 2018 *)
PROG
(C++) See the link.
KEYWORD
nonn,hard
AUTHOR
Stanislav Sykora, May 30 2014
EXTENSIONS
a(1) corrected, a(19)-a(29) added by Max Alekseyev, Jul 04 2014
STATUS
approved