Sequence A76220 of OEIS enumerates (up to $n=25$) the number $a_n$ of permutations $\sigma$ of $\lbrace 1,\ldots,n\rbrace$ such that $\sigma(i)$ and $\sigma(i+1)$ are coprime for $i=1,\ldots,n-1$.

All these numbers are obviously even for $n>1$.

All these numbers are divisible by $3$ for $n\geq 3$.

All these numbers are divisible by $9$ for $n\geq 5$.

All these numbers are divisible by $5$ for $n\geq 17$.

Such a number $a_n$ is divisible by $k!$ if there are $k-1$ primes larger than $n/2$ and smaller than $n$ (the images of $1$ and of these primes in any permutation contributing to $a_n$ can be arbitrarily permuted).

The above examples suggest however better divisibility properties, suggesting the following problem:

*Given an integer $n$, what is the maximal number $k=k(n)\leq n$ such
that for every permutation $\sigma$ of $\lbrace 1,\ldots,n\rbrace$ there exists a set $\lbrace a_1,\ldots,a_k\rbrace$ of $k$ elements in $\lbrace 1,\ldots,n\rbrace$ with $\sigma(a_i)$ coprime to
$\sigma(a_j\pm 1)$ for all $i$ and $j$ (with $a_j-1$ or $a_j+1$
outside $\lbrace 1,\ldots,n\rbrace$ dropped)?*

*Can one say something meaningful on the asymptotics of $k(n)$ (e.g., has it sublinear growth)?*

Observation: We can of course assume that $a_1,\ldots,a_k$ contains the preimage of $1$ and of all primes larger than $n/2$ in $\lbrace 1,\ldots,n\rbrace$.

allpermutations, or only for those enumerated by A76220? $\endgroup$1more comment