20081105, 20:13  #1 
May 2004
New York City
2×2,099 Posts 
Permutations Yielding Primes
I permuted the first 20 positive integers such that the sum or difference
of adjacent integers is prime. This is (perhaps not surprisingly) easy, considering the number of primes < 20. Of course, odds and evens must alternate. Given that, just how likely is this property? More generally, is it always possible to permute the first N > 1 integers so that the sum or difference of adjacent integers is prime? If not, how high can we go? 
20081105, 23:57  #2 
"Richard B. Woods"
Aug 2002
Wisconsin USA
7188_{10} Posts 
For instance:
[1 2] [1 2 3] [1 2 3 4] Not necessarily, unless the sum or difference must be an odd prime. [1 2 4 3 5] [1 2 3 4 6 5] [1 2 3 4 6 5 7] [1 2 3 4 6 8 5 7] [1 2 3 4 6 8 5 7 9] [1 2 3 4 6 8 5 7 9 10] [1 2 3 4 6 11 8 5 7 9 10] [1 2 3 4 6 11 8 5 7 9 10 12] [1 2 3 4 13 6 11 8 5 7 9 10 12] [1 2 3 4 13 6 11 8 5 7 9 10 12 14] [1 2 3 4 13 6 11 8 5 7 9 10 12 14 15] [1 2 3 4 13 6 11 8 5 7 9 10 12 14 15 16] [1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 15 16] [1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 15 16 18] [1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 15 16 18 19] [1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 20 15 16 18 19] [1 2 3 4 13 6 11 8 5 7 9 10 12 14 17 20 15 16 18 19 21] Last fiddled with by cheesehead on 20081106 at 00:08 
20081106, 14:31  #3 
May 2004
New York City
2×2,099 Posts 
You're right, if ANY prime is ok (including 2) then it's always easy,
e.g. [19,17,15,13,11,9,7,5,3,1,2,4,6,8,10,12,14,16,18,20]. My comment about alternation missed this. 
20081107, 00:43  #4 
Feb 2006
Denmark
2·5·23 Posts 
Start with [1 6 3 8 5 2 7 4 9] which contains 1 to 9. Then repeat the 8 differences (which are all +/3 or +/5) forever. This gives an infinite solution, and finite solutions for all N of form 8m+1 or 8m. Other N values of form 8m+k can be reached by starting with a solution for k which ends with k, and then repeating the difference pattern.

20081107, 09:03  #5 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}·3·599 Posts 
So, in order to be challenging the rule needs to require that a certain proportion of the formed primes be sums rather than differences.

20081107, 12:45  #6  
Dec 2007
Cleves, Germany
2×5×53 Posts 
Quote:
2 1  4 3  8 5 6 7  10 9  14 17 12 11 18 13 16 15  22 19 24 23 20 21  ... The pipe symbols mark subsolutions for N=2, N=4, N=8, N=10, N=18, and N=24. 

20081107, 18:15  #7 
Feb 2006
Denmark
2×5×23 Posts 
For prime sums, see http://primepuzzles.net/puzzles/puzz_176.htm which is about circles, corresponding to the first and last number in a sequence being adjacent.
See also A051252. Last fiddled with by Jens K Andersen on 20081107 at 18:19 Reason: Add OEIS link 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
How To Find The Formula of This Permutations?  dini  Puzzles  0  20090322 03:39 
permutations  davieddy  Puzzles  27  20070715 22:06 
PrimeForm yielding few results  problem with equation?  roger  Information & Answers  1  20061015 03:50 
Number of nelement permutations with exactly k inversions  tytus  Math  3  20050204 10:10 