A242529 Number of cyclic arrangements (up to direction) of numbers 1,2,...,n such that any two neighbors are coprime.

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

Author

Stanislav Sykora, May 30 2014

Keywords

• nonn
• hard

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.

Examples

			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}.
		

Links

• S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.
• Wikipedia, Coprime integers

Crossrefs

Cf. A242519, A242520, A242521, A242522, A242523, A242524, A242525, A242526, A242527, A242528, A242530, A242531, A242532, A242533, A242534.

Programs

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 *)

Formula

For n>2, a(n) = A086595(n)/2.

Extensions

a(1) corrected, a(19)-a(29) added by Max Alekseyev, Jul 04 2014