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

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

Author

Bob Andriesse, Jan 10 2024

Keywords

• nonn
• more

Comments

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.

Examples

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

Links

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

Crossrefs

Cf. A076220, A103839, A367704.

Programs

Mathematica

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

PARI

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); }

Python

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

Extensions

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