A368958 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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