# Permutations of the set $\{1,2,…,n\}$ and prime numbers

I just observed for some small $n$ that we can find a permutation of the set $\{1,2,...,n\}$ which is such that sum of any two adjacent numbers is a prime number.

Take for example set $\{1,2,3,4,5,6\}$ and permute it to get $\{1,4,3,2,5,6\}$. Then we have $1+4=5$ and $4+3=7$ and $3+2=5$ and $2+5=7$ and $5+6=11$ so the sum of any two adjacent numbers is a prime number.

So naturally I asked myself could it be that there is some infinite set $\{n_i:i \in \mathbb N\}$, a subset of the set of natural numbers, such that every set of these sets $\{\{1,2,...,n_i\}:i \in \mathbb N\}$ can be permuted in at least one way to obtain a set that has the property that the sum of every two adjacent numbers is a prime number.

Can it be that such set exists? Or some known or conjectured fact forbids its existence?

• The question seems quite clear to me: Are there infinitely many natural numbers $n_i$ such that $\{1,2,\ldots,n_i\}$ can be permuted such that the sums of adjacent numbers are prime? – joriki Jun 2 '16 at 22:58
• It's possible at least up to $n=11$. 2 : [1, 2] 3 : [1, 2, 3] 4 : [1, 2, 3, 4] 5 : [1, 4, 3, 2, 5] 6 : [1, 4, 3, 2, 5, 6] 7 : [1, 2, 3, 4, 7, 6, 5] 8 : [1, 2, 3, 4, 7, 6, 5, 8] 9 : [1, 2, 3, 4, 7, 6, 5, 8, 9] 10 : [1, 2, 3, 4, 7, 6, 5, 8, 9, 10] 11 : [1, 2, 3, 4, 7, 10, 9, 8, 5, 6, 11] – joriki Jun 2 '16 at 23:05
• @Farewell Suppose $n+1$ and $n+3$ are twin primes. Then placing the numbers in the form $1,n,3,n-2,5,n-4.,...,n-1,2$ does the trick. And most people believe there is an infinite number of twin primes. In fact we might be able to get somewhere using one of the following classes is infinite: twin primes, sexy primes, cousin primes. – Jorge Fernández Hidalgo Jun 2 '16 at 23:14
• @Farewell If it does generalize to cousin primes, then perhaps it can be generalized further? It is known that there exists $k < 250$ such that there are infinitely many prime pairs $(p,p+k)$. – Erick Wong Jun 2 '16 at 23:24
• Next few values: 17536, 23296, 74216, 191544, 2119632, 4094976, 24223424, 45604056 for $n=12,13,\ldots, 19$. – Erick Wong Jun 2 '16 at 23:57

This is still incomplete, but it may help:

We say $n$ is prime-permutable if we can permute $\{1,2,3\dots n\}$ so that the sum of adjacent terms is prime.

We wish to determine wheter the set $M$ of prime-permutable integers is finite or infinite. ( but if we can it would be great).

If it is finite we probably won't be able to prove it since if $n+1$ and $n+3$ are twin primes then $n$ is permutable, via the permutation:

$1,n,3,n-2,5,\dots, n-1,2$.

The number of suitable permutations for $n\leq 12$ is:

$2 : 2$

$3 : 2$

$4 : 8$

$5 : 4$

$6 : 16$

$7 : 24$

$8 : 60$

$9 : 140$

$10 : 1328$

$11 : 2144$

$12 : 17536$

$13 : 23296$

$14 : 74216$

$15 : 191544$

$16 : 2119632$

$17 : 4094976$

$18 : 24223424$

$19 : 45604056$

• Can you call such an $n$ a "prime-permutable" number? It seems more descriptive than "permutable". – Farewell Jun 2 '16 at 23:43
• you've got it.${}{}{}{}$ – Jorge Fernández Hidalgo Jun 2 '16 at 23:48
• @CarryonSmiling: If I am understanding your answer correctly, a sufficient (but not necessary) condition for $n$ to be prime-permutable is that both $n+1$ and $n+3$ are prime. Does this question then have some connection to the twin prime conjecture? (It is certainly a consequence of it.) – Nicholas Stull Jun 3 '16 at 0:06
• yes, if the twin prime conjecture holds then $M$ is infinite. – Jorge Fernández Hidalgo Jun 3 '16 at 0:07
• @CarryonSmiling Maybe it would be nice that you add in the answer to your values the values obtained by Erick Wong for n=12,13,...,19, and you could also next to each number of permutations give what approximately percentage is the number of valid permutations relative to the number of all permutations, just to have a slightly bigger picture. – Farewell Jun 3 '16 at 0:17