21
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean the sum of any two neighbouring numbers adds up to a prime? $\endgroup$ – Ian Coley Jan 27 '14 at 21:47
  • $\begingroup$ @IanColey Yes Ian! I wrote a program to find out if its possible to generate such series. For certain values of n, I'm not able to generate the correct sequence based on my Algorithm. So the only way to find out if it's actually possible to do so or if my Algorithm is faulty is to prove it with a theorem. But my weak Math skills require me to ask for help $\endgroup$ – user6123723 Jan 27 '14 at 21:50
  • 2
    $\begingroup$ My gut feeling is that proving such a theorem is beyond the scope of 21st-century mathematics. $\endgroup$ – TonyK Jan 27 '14 at 21:59
  • 1
    $\begingroup$ @benh Finding a working sequence like you did is why I wanted a failed one. Good answer below as well. $\endgroup$ – John Habert Jan 28 '14 at 13:35
  • 1
    $\begingroup$ @user1324816 they already had the results I rediscovered: the prime twins trick and a version of the lemma. They even discuss something about a "Bertrand's postulate". The Hamiltonian path approach is also not new. I emailed the guy who wrote the problem for Index to Mathematical Problems, Edward Wang, about this and I'm waiting an answer from him. BTW, we now know a permutation always exists up to $10^{262}$. $\endgroup$ – Ian Mateus Feb 5 '14 at 2:03
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you clarify what is the difficulty? Wouldn't it always end with $3 - (p-1) - 1 - (p+1)$? $\endgroup$ – Calvin Lin Jan 28 '14 at 0:18
  • $\begingroup$ @CalvinLin I updated the post. $\endgroup$ – Ian Mateus Jan 28 '14 at 15:27
  • $\begingroup$ @IanMateus Trying to digest your answer. Will report back when my feeble brain is able to make sense of all this math! $\endgroup$ – user6123723 Jan 28 '14 at 22:41
  • 1
    $\begingroup$ @user1324816 An important remark is that the algorithm used to prove the main theorem can be adapted to find explicit nice sequences. Suppose we want to find a nice sequence of length $n$ and we know $n$ is connectable. If there is a prime twin $p$ less than $2n$, then by using the algorithm it is sufficient to find a nice sequence of length $p-n+1$. If they are close, such as $n=92$ and $p=101$ are, this reduces our goal to finding a sequence of length $101-92+1=10$, way better than finding for $92$. After this great reduction, you can probably mix it with benh's algorithm for faster results. $\endgroup$ – Ian Mateus Jan 29 '14 at 0:04
  • 1
    $\begingroup$ In your definition of connectible, you refer to $m$. Should that be $n$? $\endgroup$ – Ross Millikan Jan 30 '14 at 17:43
19
$\begingroup$

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

enter image description here

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ I'm just... wow. Great answer. +1 $\endgroup$ – Patrick Da Silva Jan 27 '14 at 23:11
  • 1
    $\begingroup$ Patrick Da Silva: Many thanks :) @user1324816 Yes, but for the data structure you may choose any existing library (or any standard way to represent graphs). Concerning the Hamiltonian path search, there are not only optimized exact algorithms but lots of randomized algorithms which are really fast. I implemented one and found that for $n<100$ the graph $G_n$ has always a Hamiltonian path. I can share the code if you like, but unlike your own code, mine is in Python. $\endgroup$ – benh Jan 28 '14 at 1:54
  • 1
    $\begingroup$ Yes, I created an MSE repo. It has an implementation of a Hamiltonian path search for the mentioned prime graphs in Python 2.7. Have fun with the code :). github.com/bheuer/MSE/blob/master/… By the way, I checked up to $n\leq 1000$ and there was always a Hamiltonian path. $\endgroup$ – benh Jan 28 '14 at 3:35
  • 1
    $\begingroup$ benh, what happens if we require $n$ is at the start of the path? If it is still a feasible algorithm, I think we can glue our algorithms for further improvement. $\endgroup$ – Ian Mateus Jan 29 '14 at 15:44
  • 1
    $\begingroup$ @IanMateus Hey Ian, I added a parameter to fix the first element of the sequence. You can use the code from the repo if you like. $\endgroup$ – benh Jan 30 '14 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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