A076220 -id:A076220 - cp's OEIS frontend

A086595 Number of ways to arrange the numbers 1..n in a circle (up to direction) such that every two adjacent numbers are relatively prime.

1, 1, 2, 2, 12, 4, 72, 72, 720, 576, 22032, 7776, 476928, 400896, 6352992, 8515584, 805146624, 279023616, 36481536000, 23627980800, 881012367360, 1065509240832, 192859121664000, 65362194432000, 10489384048435200, 12214493322854400, 981016943829811200, 937734333109862400, 268367392739686809600

Offset: 1

Lior Manor, Jul 23 2003

nonn

a(n) is also the number of permutations of 2..n such that every two adjacent numbers are relatively prime.

			a(6) = 4 since there are 4 ways to arrange 1,2,3,4,5,6 in a circle such that every two adjacent numbers are relatively prime: 1-2-3-4-5-6-1, 1-4-3-2-5-6-1, 1-6-5-2-3-4-1, 1-6-5-4-3-2-1.

Cf. A076220.

{ A086595(n) = my(d, A, r, M); A=matrix(n,n,i,j,gcd(i,j)==1); r=0; forstep(s=1,2^n-1,2, M=vecextract(A,s,s)^n; d=matsize(M)[1]; r+=(-1)^(n-d)*M[1,1]); r } /* Max Alekseyev, Jun 13 2005 */

For prime p, a(p)=A076220(p-1). - Max Alekseyev, Jun 13 2005

a(15) and a(16) from Ray Chandler and Joshua Zucker, Apr 10 2005

a(17)-a(29) from Max Alekseyev, Jun 13 2005, Jul 05 2014

A103839 Number of permutations of (1,2,3,...,n) where each of the (n-1) adjacent pairs of elements sums to a prime.

Original entry on oeis.org

1, 2, 2, 8, 4, 16, 24, 60, 140, 1328, 2144, 17536, 23296, 74216, 191544, 2119632, 4094976, 24223424, 45604056, 241559918, 675603568, 8723487720, 22850057800, 285146572432, 859834538938, 8276479696196, 32343039694056, 429691823372130

Offset: 1

N. J. A. Sloane, Mar 30 2005

nonn

The number of Hamiltonian paths in a graph of which the nodes represent the numbers (1,2,3,...,n) and the edges connect each pair of nodes that add up to a prime. - Bob Andriesse, Oct 04 2020

While A076220(n) > a(n) for 2A076220(n) / a(n) < A076220(n-1) / a(n-1). - Bob Andriesse, Dec 05 2023

			For n = 5, we have the 4 permutations and the sums of adjacent elements:
1,4,3,2,5 (1+4=5, 4+3=7, 3+2=5, 2+5=7)
3,4,1,2,5 (3+4=7, 4+1=5, 1+2=3, 2+5=7)
5,2,1,4,3 (5+2=7, 2+1=3, 1+4=5, 4+3=7)
5,2,3,4,1 (5+2=7, 2+3=5, 3+4=7, 4+1=5)

Cf. A051239, A051252.

A103839[n_] := Count[Map[lpf, Permutations[Range[n]]], 0]
lpf[x_] := Length[Select[asf[x], ! PrimeQ[#] &]];
asf[x_] := Module[{i}, Table[x[[i]] + x[[i + 1]], {i, Length[x] - 1}]];
Table[A103839[n], {n, 1, 9}] (* Robert Price, Oct 25 2018 *)

okperm(perm) = {for (k=1, #perm -1, if (! isprime(perm[k]+perm[k+1]), return (0));); return (1);}
a(n) = {nbok = 0; for (j=1, n!, perm = numtoperm(n, j); if (okperm(perm), nbok++);); return (nbok);} \\ Michel Marcus, Apr 08 2013

For n>1, a(n) = 2 * A051239(n).

More terms from Max Alekseyev, Jan 04 2008

a(25)-a(28) from Giovanni Resta, Apr 01 2014

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

A367704 Number of permutations of [n] where each pair of adjacent elements differs by a prime.

Original entry on oeis.org

1, 1, 0, 0, 2, 10, 32, 96, 448, 1968, 7320, 21516, 118938, 662742, 4556360, 26950038, 155388246, 756995286, 5730299976, 38809702892, 337875402936, 2593543573702, 20560179519176, 138677553274430, 1337517942958934, 11083936316867572, 94288296012340842

Offset: 0

Bob Andriesse, Nov 27 2023

nonn

This sequence was inspired by A103839 and the PARI program is a modified version of the one in A103839.
The number of Hamiltonian paths in a graph of which the nodes represent the numbers (1,2,3,...,n) and the edges connect each pair of nodes that differ by a prime.
A076220, A103839 and this sequence are closely related, but their combined graph in the link shows an interesting difference, notably between this sequence and the two others. - Bob Andriesse, Dec 03 2023

			a(4) = 2: 2413, 3142.
a(5) = 10: 13524, 14253, 24135, 25314, 31425, 35241, 41352, 42531, 52413, 53142.

Bob Andriesse, Combined graph of this sequence, A076220 and A103839 for a(4) to a(25)

Cf. A076220, A103839.

okperm(perm) = {for (k=1, #perm -1, if (! isprime(abs(perm[k]-perm[k+1])),  return (0));  ); return (1); }
a(n) = {nbok = 0; for (j=1, n!, perm = numtoperm(n, j); if (okperm(perm), nbok++); ); return (nbok); }

a(14)-a(22) from Alois P. Heinz, Nov 27 2023

a(23)-a(26) from Martin Ehrenstein, Dec 03 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

A368958 Number of permutations of [n] where each pair of adjacent elements is coprime and does not differ by a prime.

Original entry on oeis.org

1, 1, 2, 2, 2, 10, 4, 28, 6, 42, 40, 348, 42, 1060, 226, 998, 886, 21660, 690, 57696, 4344, 26660, 22404, 1091902, 12142, 1770008

Offset: 0

Bob Andriesse, Jan 10 2024

The number of Hamiltonian paths in a graph of which the nodes represent the numbers (1,2,3,...,n) and the edges connect each pair of nodes that are coprime and do not differ by a prime.

			a(5) = 10: 15432, 21543, 23451, 32154, 34512, 43215, 45123, 51234, 54321, 12345.
a(6) = 4: 432156, 651234, 654321, 123456.

Bob Andriesse, Combined graph of this sequence, A076220, A103839 and A367704 for a(4) to a(25).

Cf. A076220, A103839, A367704.

a[n_] := a[n] = Module[{b = 0, ps}, ps = Permutations[Range[n]]; Do[If[Module[{d}, AllTrue[Partition[pe, 2, 1], (d = Abs[#[[2]] - #[[1]]]; ! PrimeQ[d] && CoprimeQ[#[[1]], #[[2]]]) &]], b++], {pe, ps}]; b];
Table[a[n], {n, 0, 8}] (* Robert P. P. McKone, Jan 12 2024 *)

okperm(perm) = {for(k=1, #perm-1, if((isprime(abs(perm[k]-perm[k+1]))), return(0)); if(!(gcd(perm[k], perm[k+1])==1), return(0));); return(1);}
a(n) = {my(nbok = 0); for (j=1, n!, perm = numtoperm(n,j); if(okperm(perm), nbok++);); return(nbok); }

from math import gcd
from sympy import isprime
def A368958(n):
    if n<=1 : return 1
    clist = tuple({j for j in range(1,n+1) if j!=i and gcd(i,j)==1 and not isprime(abs(i-j))} for i in range(1,n+1))
    def f(p,q):
        if (l:=len(p))==n-1: yield len(clist[q]-p)
        for d in clist[q]-p if l else set(range(1,n+1))-p:
            yield from f(p|{d},d-1)
    return sum(f(set(),0)) # Chai Wah Wu, Jan 19 2024

a(14)-a(25) from Alois P. Heinz, Jan 11 2024

A109813 Number of permutations of (the positive integers <= n and coprime to n), where each element of the permutations is coprime to its adjacent elements.

Original entry on oeis.org

1, 1, 2, 2, 12, 2, 72, 24, 144, 12, 22032, 24, 476928, 480, 1728, 9600, 805146624, 720, 36481536000, 30240, 1728000, 312000, 192859121664000, 40320, 2159795404800, 46293120, 249684249600, 58423680

Offset: 1

Leroy Quet, Aug 16 2005

Sequence continues: a(29) = ?, 40320, ?, 1893397524480, 32006016000000, 478511953920, ?, 209018880, ?, 122634632171520, ?, 665481277440, ?, 399168000. - Franklin T. Adams-Watters, Sep 25 2006

			The integers coprime to 10 and <= 10 are (1,3,7,9).
Of the permutations of these integers, there are 12 permutations where all adjacent terms are coprime, i.e., where 3 and 9 are not adjacent. So the 10th term of the sequence is 12.

Cf. A076220.

{A109813(x)=local(v, A, d, r, M, i, j); n=eulerphi(x); v=vector(n,i,0); j=0; for(i=1,x,if(gcd(i,x)==1,j++;v[j]=i)); A=matrix(n, n, i, j, gcd(v[i], v[j])==1); 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} \\ Franklin T. Adams-Watters, Sep 25 2006

More terms from Franklin T. Adams-Watters, Sep 25 2006

A117541 Number of permutations P of 1..n such that in P and in the inverse of P, every pair of adjacent numbers are relatively prime.

Original entry on oeis.org

1, 2, 6, 9, 56, 23, 399, 442, 2220, 2386, 71577, 22001, 1179483, 1156519, 4975079

Offset: 1

Giovanni Resta, Mar 28 2006

nonn

Sequence suggested by Leroy Quet on the SeqFan mailing list.

			a(4)=9, since the 9 permutations (1,2,3,4), (1,4,3,2), (2,1,3,4), (2,1,4,3), (2,3,4,1), (4,1,2,3), (3,2,1,4), (3,4,1,2), (4,3,2,1) satisfy the property.

Cf. A076220, A117542.

cp's OEIS Frontend

A086595 Number of ways to arrange the numbers 1..n in a circle (up to direction) such that every two adjacent numbers are relatively prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

Extensions

A103839 Number of permutations of (1,2,3,...,n) where each of the (n-1) adjacent pairs of elements sums to a prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

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

A367704 Number of permutations of [n] where each pair of adjacent elements differs by a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

A368958 Number of permutations of [n] where each pair of adjacent elements is coprime and does not differ by a prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica