Skip to main content
3 of 4
replaced http://math.stackexchange.com/ with https://math.stackexchange.com/

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