Permutations Yielding Primes

[davar55]

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?

[cheesehead]

For instance:

[1 2]

[1 2 3]

[1 2 3 4]

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]

[davar55]

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.

[Jens K Andersen]

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.

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

[ckdo]

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.

[Jens K Andersen]

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.

[cheesehead]

A055265 is related.