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,3

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.

Links

Table of n, a(n) for n=0..25.

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

Example

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

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

Prog

(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

Crossrefs

Cf. A076220, A103839, A367704.

Sequence in context: A324956 A268081 A319885 * A125695 A152681 A215603

Adjacent sequences: A368955 A368956 A368957 * A368959 A368960 A368961

Keyword

nonn,more

Author

Bob Andriesse, Jan 10 2024

Extensions

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

Status

approved