A086595 -id:A086595 - cp's OEIS frontend

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

Stanislav Sykora, May 30 2014

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.

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

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

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

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

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

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

A076220 Number of permutations of 1..n in which every pair of adjacent numbers are relatively prime.

Original entry on oeis.org

1, 1, 2, 6, 12, 72, 72, 864, 1728, 13824, 22032, 555264, 476928, 17625600, 29599488, 321115392, 805146624, 46097049600, 36481536000, 2754120268800, 3661604352000, 83905105305600, 192859121664000, 20092043520000000, 15074060547686400, 1342354557616128000

Offset: 0

Lior Manor, Nov 04 2002

nonn

			a(4) = 12 since there are 12 permutations of 1234 in which every 2 adjacent numbers are relatively prime: 1234, 1432, 2134, 2143, 2314, 2341, 3214, 3412, 4123, 4132, 4312, 4321.

Cf. A086595.

with(combinat): for n from 1 to 7 do P:=permute(n): ct:=0: for j from 1 to n! do if add(gcd(P[j][i+1],P[j][i]),i=1..n-1)=n-1 then ct:=ct+1 else ct:=ct fi od: a[n]:=ct: od: seq(a[n],n=1..7); # Emeric Deutsch, Mar 28 2005
# second Maple program:
b:= proc(s, t) option remember; `if`(s={}, 1, add(
      `if`(igcd(i, t)>1, 0, b(s minus {i}, i)), i=s))
    end:
a:= n-> b({$1..n}, 1009):
seq(a(n), n=0..14);  # Alois P. Heinz, Aug 13 2017

f[n_] := Block[{p = Permutations[ Table[i, {i, 1, n}]], c = 0, k = 1}, While[k < n! + 1, If[ Union[ GCD @@@ Partition[p[[k]], 2, 1]] == {1}, c++ ]; k++ ]; c]; Do[ Print[ f[n]], {n, 2, 15}]

{A076220(n)=local(A, d, n, r, M); A=matrix(n,n,i,j,if(gcd(i,j)==1,1,0)); r=0; for(s=1,2^n-1,M=vecextract(A,s,s)^(n-1);d=matsize(M)[1];r+=(-1)^(n-d)*sum(i=1,d,sum(j=1,d,M[i,j])));r} \\ Max Alekseyev, Jun 12 2005

a(p-1) = A086595(p) for prime p. - Max Alekseyev, Jun 12 2005

Extended by Frank Ruskey, Nov 11 2002
a(15)-a(16) from Ray Chandler and Joshua Zucker, Apr 10 2005
a(17)-a(24) from Max Alekseyev, Jun 12 2005
a(0) prepended and a(25) added by Alois P. Heinz, Aug 13 2017

A102381 Number of permutations of 1..n in which every pair of adjacent numbers as well as the first and the last entries are relatively prime.

Original entry on oeis.org

1, 2, 6, 8, 60, 24, 504, 576, 6480, 5760, 242352, 93312, 6200064, 5612544, 95294880, 136249344, 13687492608, 5022425088, 693149184000, 472559616000, 18501259714560, 23441203298304, 4435759798272000, 1568692666368000, 262234601210880000, 317576826394214400

Offset: 1

Emeric Deutsch (in collaboration with Ray Chandler, Vladeta Jovovic, Leroy Quet, Zak Seidov, and Joshua Zucker), Apr 09 2005

nonn

a(n) = n*A086595(n).

			a(4)=8 because we have 1234, 1432, 2143, 2341, 3214, 3412, 4123 and 4321.

Cf. A086595, A076220.

with(combinat): for n from 1 to 7 do P:=permute(n): ct:=0: for j from 1 to n! do if add(gcd(P[j][i+1],P[j][i]),i=1..n-1)=n-1 and gcd(P[j][1],P[j][n])=1 then ct:=ct+1 else ct:=ct fi od: a[n]:=ct: od: seq(a[n],n=1..7);

{1}~Join~Array[Count[Permutations@ Range@ #, w_ /; AllTrue[Map[ RotateLeft[w, #][[1 ;; 2]] &, w], CoprimeQ @@ # &]] &, 8, 2] (* Michael De Vlieger, Sep 25 2017 *)

a(15) and a(16) from Ray Chandler and Joshua Zucker, Apr 12 2005
a(17)-a(24) from Max Alekseyev, Jun 13 2005
a(25)-a(26) (using A086595) from Alois P. Heinz, May 05 2023

A107761 Number of permutations of (1,3,5,7,9,...,2n-1) where every adjacent pair in the permutation are coprime.

Original entry on oeis.org

1, 2, 6, 24, 72, 480, 3600, 9600, 108000, 1270080, 4795200, 74088000, 768539520, 4759413120, 94182359040, 1893397524480, 11353661706240, 122634632171520, 3104438623534080, 23063946114908160, 664424069072117760

Offset: 1

Ray Chandler, following a suggestion of Leroy Quet, Jun 11 2005

nonn

Odd analog of A076220.

			For example, if n = 5, the permutation (5,3,7,9,1) is counted, but (5,3,9,1,7) is not counted because 3 and 9 are adjacent.

Cf. A076220, A086595, A102381, A107762, A107763.

With[{n=9}, per=Permutations[Range[1, 2 n -1, 2]]; Select[per, Times @@ Table[GCD @@Partition[ #, 2, 1][[i]], {i, n-1}]==1&]//Length] (Seidov)

a(1)-a(9) computed by Zak Seidov.

More terms from Max Alekseyev, Jun 11 2005

A107762 Number of permutations of (1,3,5,7,9,...,2n-1) in which every pair of adjacent numbers as well as the first and the last entries are relatively prime.

Original entry on oeis.org

1, 2, 6, 24, 60, 432, 3360, 6912, 86400, 1080000, 3432000, 57542400, 601810560, 3374784000, 71391196800, 1506917744640, 8134703216640, 87731370397440, 2330058011258880, 15991083879321600, 484342868413071360

Offset: 1

Ray Chandler, Jun 11 2005

nonn

Odd analog of A102381. Equals n*A107763(n).

Cf. A076220, A086595, A102381, A107761, A107763.

More terms from Max Alekseyev, Jun 11 2005

A107763 Number of ways to arrange the numbers (1,3,5,7,9,...,2n-1) in a circle such that every two adjacent numbers are relatively prime.

Original entry on oeis.org

1, 1, 2, 6, 12, 72, 480, 864, 9600, 108000, 312000, 4795200, 46293120, 241056000, 4759413120, 94182359040, 478511953920, 4873965022080, 122634632171520, 799554193966080, 23063946114908160, 664424069072117760, 3198456730188840960, 108184656752428032000, 2657146152621477888000, 22850984107452933734400, 863305241854715928576000, 15282315334192501724774400, 151673086024479840160972800

Offset: 1

Ray Chandler, Jun 11 2005

nonn

Odd analog of A086595.

Cf. A076220, A086595, A102381, A107761, A107762.

More terms from Max Alekseyev, Jun 11 2005

a(23)-a(29) from Max Alekseyev, Jul 08 2014

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A076220 Number of permutations of 1..n in which every pair of adjacent numbers are relatively prime.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A102381 Number of permutations of 1..n in which every pair of adjacent numbers as well as the first and the last entries are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A107761 Number of permutations of (1,3,5,7,9,...,2n-1) where every adjacent pair in the permutation are coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A107762 Number of permutations of (1,3,5,7,9,...,2n-1) in which every pair of adjacent numbers as well as the first and the last entries are relatively prime.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A107763 Number of ways to arrange the numbers (1,3,5,7,9,...,2n-1) in a circle such that every two adjacent numbers are relatively prime.

Views

Author

Keywords

Comments

Crossrefs

Extensions