cp's OEIS Frontend

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

%I A368958 #31 Jan 19 2024 20:33:50
%S A368958 1,1,2,2,2,10,4,28,6,42,40,348,42,1060,226,998,886,21660,690,57696,
%T A368958 4344,26660,22404,1091902,12142,1770008
%N A368958 Number of permutations of [n] where each pair of adjacent elements is coprime and does not differ by a prime.
%C A368958 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.
%H A368958 Bob Andriesse, <a href="/A368958/a368958.jpg">Combined graph of this sequence, A076220, A103839 and A367704 for a(4) to a(25)</a>.
%e A368958 a(5) = 10: 15432, 21543, 23451, 32154, 34512, 43215, 45123, 51234, 54321, 12345.
%e A368958 a(6) = 4: 432156, 651234, 654321, 123456.
%t A368958 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];
%t A368958 Table[a[n], {n, 0, 8}] (* _Robert P. P. McKone_, Jan 12 2024 *)
%o A368958 (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);}
%o A368958 a(n) = {my(nbok = 0); for (j=1, n!, perm = numtoperm(n,j); if(okperm(perm), nbok++);); return(nbok); }
%o A368958 (Python)
%o A368958 from math import gcd
%o A368958 from sympy import isprime
%o A368958 def A368958(n):
%o A368958     if n<=1 : return 1
%o A368958     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))
%o A368958     def f(p,q):
%o A368958         if (l:=len(p))==n-1: yield len(clist[q]-p)
%o A368958         for d in clist[q]-p if l else set(range(1,n+1))-p:
%o A368958             yield from f(p|{d},d-1)
%o A368958     return sum(f(set(),0)) # _Chai Wah Wu_, Jan 19 2024
%Y A368958 Cf. A076220, A103839, A367704.
%K A368958 nonn,more
%O A368958 0,3
%A A368958 _Bob Andriesse_, Jan 10 2024
%E A368958 a(14)-a(25) from _Alois P. Heinz_, Jan 11 2024