The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A368958 Number of permutations of [n] where each pair of adjacent elements is coprime and does not differ by a prime. 2
 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 21 19:35 EDT 2024. Contains 372738 sequences. (Running on oeis4.)