CODEWITHSUNDEEP
algorithmpermutationprimes
Prashanth Kumar
Prashanth Kumar

Reputation: 51

Print sequences with prime sum

Given an integer n, I want to find two permutations of the numbers 1 to n (inclusive) such that the sum of numbers from the two permutations at any given index is always prime.

For example:

   n = 5

      1 2 3 4 5
      1 5 4 3 2

   n = 8

      1 2 3 4 5 6 7 8
      2 1 4 3 8 7 6 5

Upvotes: 5

Views: 89

Answers (2)

Dave
Dave

Reputation: 9085

Find the smallest number k>=1 such that n+k is prime.

Form pairs: (n,k), (n-1, k+1), ..., (k,n).

If k>1, repeat on the range [1,k].

E.g., n=5: 5+2=7, so we have:

5, 4, 3, 2
2, 3, 4, 5

Then we repeat for 1.

E.g. n=8: 8+3 = 11, so we have:

8, 7, 6, 5, 4, 3
3, 4, 5, 6, 7, 8

Leaving us with 2:

1, 2
2, 1

By Bertrand's postulate aka Chebyshev's theorem, for any n>1 there is a prime p s.t. n < p < 2n, and for n=1 we have 1+1=2, so we will always be able to do this.

Upvotes: 2

Paul Hankin
Paul Hankin

Reputation: 58319

Construct a bipartite graph on {0,1} x {1...n} such that (0, i) and (1, j) are connected if and only if i+j is prime.

Find a perfect matching using any standard technique, and then produce the sequences so that the matching numbers are at the same index.

Upvotes: 2

Related Questions