How to either prove or disprove if it is possible to arrange a series of numbers such the sum of any two adjacent number adds up to a prime number

Question

I'm wondering if it's possible to write a theorem to prove or disprove the possibility of arranging a sequence of numbers (1,2,...n) such that the sum of any two numbers adds up to a prime number.

An Example:

Input: Say n=7. The sequence is 1,2,3,4,5,6,7

Output: 7,6,5,2,1,4,3

Here are a few numbers where a program I wrote seems to fail for

n=71
solution sequence:
36 37 52 61 18 19 54 55 58 45 56 11 26 27 44 53 60 67 6 7 10 13 30 31 48 49 64 3 4 15 16 21 22 25 28 33 34 39 40 43 46 51 62 65 66 71 2 5 8 9 14 17 20 23 24 29 32 35 38 41 42 47 50 63 68 69 70 1 12 59 
 But unable to fit: 57 

n=50
solution sequence:
19 12 49 30 31 48 11 50 3 4 15 38 41 42 47 6 7 10 13 18 23 24 29 32 35 44 45 2 5 8 9 14 17 20 21 22 25 28 33 34 39 40 43 46 1 36 
But unable to fit: 37 27 26 16 

Successful attempts:

n=17
3 4 7 10 13 6 11 12 17 2 5 8 9 14 15 16 

n=25
23 24 19 12 11 18 25 6 7 10 13 16 3 4 15 2 5 8 9 14 17 20 21 22 1

Here is the program (very dirty I warn you!) I wrote to be able to generate the above output. Hint: Change max to the number you want and try it out.

Answer 1

Every number $n\leq 10^{262}$ is interesting, a property that guarantees a permutation of $\{1,2,\ldots, n\}$ such that the sum of any adjacent numbers is a prime number. This lower bound for a non interesting number was computed by Charles.

A number $n$ is interesting if there is a permutation of $\{1,2,3,\ldots,n\}$ that either starts or ends with $n$ and the sum of any adjacent numbers is a prime number. Such a permutation is also called interesting.

---

Theorem. If $(p, p+2)$ is a prime pair, then $p$ and $p+1$ are always interesting. Moreover, if $k\leq (p+1)/2$ is interesting, then $p+1-k$ is interesting.

For the $p+1$ and $p$ cases, use the sequence $S_p=(a_n)_{n=1}^p$ defined by $a_{2k-1}=2k-1$ and $a_{2k}=p-(2k-1)$. The sequence $S_p$ is always interesting. The results can only be $p$ or $p+2$, and they are prime by hypothesis. Because $a_p=p$ and $a_1=1$, we can always create a new interesting sequence $S'$ of length $p+1$. $\square$

To show that if $k\leq (p+1)/2$ interesting, then $p+1-k$ is interesting, we will use the following algorithm to create an interesting sequence of length $p-k+1$ from $S_p$. Firstly, note that $a_{k}+a_{p+1-k}=p+1$.

Find a sequence $S'$ by deleting the terms $a_m$ from $S_p$ such that $m\leq k-1$ or $m\geq p-(k-1)$. The set of deleted numbers is the union of the disjoint sets $I_{k-1}=\{1,2,\ldots,k-1\}$ and $I_p\setminus I_{p-k+1}=\{p-(k-1)+1, p-(k-1)+2,\ldots, p\}$. Notice that $k$ is either $a_{k}$ (if $k$ is odd) or $a_{p-k}$ (if $k$ is even). Construct an interesting sequence $T_{k}$ of length $k$ and connect $T_k$ and $S'$ by $k$. The new sequence is a permutation of $$I_k\cup\left(I_{p}\setminus\left(I_{k-1}\cup I_p\setminus I_{p-k+1}\right)\right)=I_{p-k+1}$$ and it is interesting because $p-k+1$ is at the other extreme of the sequence. $\square$

---

Applying the theorem a bit, we see that because $1$, $2$, $3$, $4$ and $5$ are interesting, then every $n\leq 18$ is interesting. We now prove the following

Lemma. If $k$ is interesting for every $k\leq N$ and there is a prime pair $(p, p+2)$ such that $p\leq 2N-1$, then every $k\leq p+1$ is interesting.

By the main theorem, $p-k+1$ is interesting for every $k\leq N$, so the numbers $\left\{p+1-\frac{p+1}{2}, p+2-\frac{p+1}{2},\ldots, p\right\}$ are interesting. By hypothesis, $p\leq 2N-1$, so $p+1-(p+1)/2\leq N$, therefore every $k\leq p+1$ is interesting.

---

Now that we've set the theoretical framework needed, we will describe a fast algorithm for finding interesting sequences. Applying the reasoning used to prove the main theorem, we will construct an interesting sequence of length $k$ from $S_p$ using another interesting sequence of length $p-n+1\leq (p+1)/2$ by the following

Algorithm.

If $n$ is interesting and there is at least one prime twin $q\leq 2n-1$, let $p$ be the least of such primes. Write $S_p=(a_k)_1^p$ and construct $S'$ by deleting $a_m$ for $m\leq p-n$ or $m\geq n$. Construct an interesting sequence $T_{p-n+1}$ of length $p-n+1$ and connect $S'$ and $T_{p-n+1}$. If $T_{p-n+1}$ is still too large to find, repeat the algorithm. The algorithm ends when the number found is sufficiently small.

The algorithm must always end if the twin primes respect Bertrand's postulate for $t\leq p$. Using the algorithm once, we constructed an implication $p-n+1\to n$. If there is a least twin prime $q\leq 2(p-n+1)-1$, the algorithm will run again to construct $q-(p-n+1)+1\to p-n+1$ and so on. This is strictly decreasing, so the algorithm must stop at the worst case in $n$ steps.

---

In practice, this is quite fast for moderately large numbers. For example, randomly take the number $n=28437$ and apply the algorithm.

The least prime twin $\geq 28437$ is $p=28547$, so we need to write down $S_{28547}$ and find a interesting sequence of length $28547-28437+1=111$. To find it, iterate the algorithm, using $n_2=111$. The next prime twin is $p_2=137$, so we write down $S_{137}$ and construct a sequence of length $137-111+1=27$. The next prime twin is $29$, so our life is easy now. Write down $S_{29}$ and find an interesting sequence $T_{27}$. Write down $S_{137}$ and find $T_{111}$ using $T_{27}$. Finish the algorithm by writing down $S_{28547}$ and finding $T_{28437}$.

In three algorithm applications, we found an interesting sequence $T_{28437}$. This is way better than a brute force approach.

We are now in position to begin the computations. We every $k\leq 18$ is interesting. Together with the prime pair $(29, 31)$, we know every $k\leq 30$ is interesting by the lemma. By iterating it, using this prime twins table and a calculator, $n$ is always interesting for $n\leq 18\times 10^6$ and probably for larger numbers.

The safe bound was strengthened by chubakueno to be $\geq 8825318188022112$ $\approx 8,8\times 10^{15}$. The best lower bound so far is a whooping $10^{165}$, found by Charles here.

The twin prime conjecture alone is not enough for proving every number is interesting, but it would be sufficient that the prime twins respect Bertrand's postulate. As long as there is a prime pair $\lt 2n$, we can always extend the results.

It turns out the analysis made here is not new: I can date these theorems back as far as $2000$ here (with no rigorous proofs, however). This is an open problem from the late seventies, so these elementary theorems are probably much older. There is little hope these methods can lead to an actual proof independently of the distribution of twin primes: attempts made to combine primes $p$ and $p+2k$ to form interesting strings have been unfruitful.

Answer 2

Not an answer but a comment on the problem:

I think the enumeration of such rearranged sequences is a graph theory question. Consider the undirected graph $G_n$ whose nodes are the numbers from $1$ to $n$. Draw an edge between $a$ and $b$ if $a+b$ is prime. Then by Bertrand's postulate you get a connected graph.

Arrangements of the numbers such that the sum of any two consecutive numbers is prime correspond to Hamiltonian paths of $G_n$. An example for $n=8$:

Note that the graph is bipartite. This gives you methods to find prime arrangements in $O(1.5^n)$ rather than $O(n!)$ as required for the brute force approach.

However I doubt that it really helps to prove for which numbers such an arrangement exists.