mersenneforum.org Permutations Yielding Primes
 Register FAQ Search Today's Posts Mark Forums Read

 2008-11-05, 20:13 #1 davar55     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?
2008-11-05, 23:57   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

718810 Posts

For instance:

[1 2]

[1 2 3]

[1 2 3 4]

Quote:
 Originally Posted by davar55 Of course, odds and evens must alternate.
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 2008-11-06 at 00:08

 2008-11-06, 14:31 #3 davar55     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.
 2008-11-07, 00:43 #4 Jens K Andersen     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.
 2008-11-07, 09:03 #5 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22·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.
2008-11-07, 12:45   #6
ckdo

Dec 2007
Cleves, Germany

2×5×53 Posts

Quote:
 Originally Posted by cheesehead So, in order to be challenging the rule needs to require that a certain proportion of the formed primes be sums rather than differences.
Here's a solution for N=24 which uses only sums. Feel free to expand on that:

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 sub-solutions for N=2, N=4, N=8, N=10, N=18, and N=24.

 2008-11-07, 18:15 #7 Jens K Andersen     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 2008-11-07 at 18:19 Reason: Add OEIS link
 2008-11-08, 04:40 #8 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 22×3×599 Posts A055265 is related.

 Similar Threads Thread Thread Starter Forum Replies Last Post emily Math 34 2017-07-16 18:44 dini Puzzles 0 2009-03-22 03:39 davieddy Puzzles 27 2007-07-15 22:06 roger Information & Answers 1 2006-10-15 03:50 tytus Math 3 2005-02-04 10:10

All times are UTC. The time now is 05:26.

Sat Oct 31 05:26:38 UTC 2020 up 51 days, 2:37, 2 users, load averages: 2.73, 2.19, 1.98