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$.

  • $\begingroup$ Notice tht you can also permute pairs of the form $(p,2p)$ where $n/3<p\leq n/2$, and so on. Doesn't this improve divisibility? $\endgroup$ Oct 24, 2022 at 16:43
  • $\begingroup$ BTW, do you want the property to be satisfied for all permutations, or only for those enumerated by A76220? $\endgroup$ Oct 24, 2022 at 16:48
  • $\begingroup$ @IlyaBogdanov No you can not permute $p$ and $2p$ in general: $p$ can have even neighbours! $\endgroup$ Oct 24, 2022 at 17:23
  • $\begingroup$ Reply to the second question of Ilya Bogdanov: One can consider both problems but it is perhaps more natural to define $k(n)$ with respect to all permutations. $\endgroup$ Oct 24, 2022 at 17:25
  • $\begingroup$ Sorry for being unclear; in the first comment I meant a permutation of $p$'s and, simultaneously, the same permutation of $2p$'s, such as $p\leftrightarrow q$ and $2p\leftrightarrow 2q$. $\endgroup$ Oct 25, 2022 at 5:50

1 Answer 1


Define $k(\sigma)$ as the maximal $k$ satisfying the requirements for that single permutation $\sigma$. Then even $\max_{\sigma\in S_n}k(\sigma)$ is sublinear in $n$.

Consider a graph on $[n]$, where edges are pairs of coprime numbers. A desired set $\{a_1,\dots,a_k\}$ corresponds to a complete bipartite subgraph with parts $V_1=\{\sigma(a_i)\colon i\in[k]\}$ and $V_2=\{\sigma(a_i\pm1)\colon i\in[k]\}$ (not exactly so; see below). The cardinalities of both parts are linear in $k$.

This means that the set $\mathbb P_n=\mathbb P\cap[n]$ is split into two parts, $Q_1$ and $Q_2$, such that the prime divisors of elements in $V_i$ are all in $Q_i$/. Minimal of such parts has a sublinear in $n$ cardinality.

Indeed, fix some number $D$ which is large but much smaller than $n$, and consider the intersections $\mathbb P_i'=\mathbb P_i'\cap [D]$. Then $$ \frac{|V_i|}n\leq \prod_{p\in\mathbb P_i'}\left(1-\frac1p\right)(1+o(1)). $$ Since one of the two products is small, the claim follows.

Correction. The statement about complete bipartite graph is not completely true in the case when $a_i\pm1$ equals some $a_j$. In this case, we put such $\sigma(a_i)$ into only one part of the bipartite graph, so that the sizes of the parts differ by a factor of at most 2; then both sizes are still linear in $k$.

  • $\begingroup$ Ilya, there is only one product (involving only factors smaller than $1$) on the right side of your inequality. $\endgroup$ Oct 25, 2022 at 7:14
  • 1
    $\begingroup$ Sorry, I forgot to divide by $n$; now corrected. There are two products: for $V_1$ and for $V_2$; their product is small, so one of them is also small. $\endgroup$ Oct 25, 2022 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.