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

Here is the version of this question that I posted on math.stackexchange a few days ago and I did not receive an answer that settles my question so I thought that maybe on this site I could get a complete answer.

First, I would like to say that I am aware of the extremely similar question of the user @David S. Newman posted here a few hours ago and also I would like to note why this is not a duplicate of that question and what are the (small) differences.

In the question by @David S. Newman he also considers the first and the last element of the permutation of the set $\{1,2,...,n\}$ as adjacent so every permutation that works in his case works also in my case but it could be that there are permutations that work in my case but do not work in his case.

Another difference from my and his question is that for my question the permutations of the set $\{1,2,...,2n+1\}$ with an odd number of elements can exist and in his case cannot exist because elements must follow either the pattern "odd,even,odd,...,odd" or the pattern "even,odd,even,...,even" so the sum of the first and last element will be even number strictly greater than $2$.

Also, another difference is that I ask for the existence of infinite number of natural numbers for which permutation where adjacent elements have prime sum exist and he asks "for which $n$" permutation where adjacent elements (+ the sum of the first and last element) have prime sum exist.

I will state the question here:

Is it true that there exists 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

I can give an example for $n=6$, the same that I gave on math.stackexchange. If we permute $\{1,2,3,4,5,6\}$ in this way $\{1,4,3,2,5,6\}$ we have that every two adjacent elements sum to a prime number because we have $1+4=5$ and $4+3=7$ and $3+2=5$ and $2+5=7$ and $5+6=11$.

It is easy to see that if an infinite number of twin primes exist then my question has an affirmative answer (as it is stated in the answer to my question on math.stackexchange) but I would like to see this question settled in a way that does not depend on unproven conjectures.

Here is the number of such permutations for some values of $n$.

• Why cannot you keep adding numbers so that the last sum is always prime? E.g.: 1,4,3,2,5,6,7,10,9,22,15... All you need is infinitely many primes – Bugs Bunny Jun 7 '16 at 14:06
• @BugsBunny All numbers from $1$ to $n$ must appear exactly once. So, the question is, are there infinitely many $n$ such that the numbers from $1$ to $n$ can be permuted so that adjacent numbers sum to a prime number. – Tony Huynh Jun 8 '16 at 0:06
• @TonyHuynh Right. It seems that Bugs interpreted my question as: "Is there an infinite subset of $\mathbb N$ such that every two adjacent elements sum to a prime number?". I thought that my question was concise enough. – Farewell Jun 8 '16 at 1:31
• Correction: It seems that he interpreted it as: "Is there an infinite subset of $\mathbb N$ such that there is some permutation of that set which gives that sum of every two adjacent elements is a prime number?" – Farewell Jun 8 '16 at 1:39
• mathoverflow.net/questions/241732/… – Bugs Bunny Jun 8 '16 at 15:21