Последовательности печати с простой суммой

Question

Учитывая целое число n, я хочу найти две перестановки чисел от 1 до n (включительно), чтобы сумма чисел из двух перестановок в любом заданном индексе всегда была проста.

Например:

   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

Answer 1

Найдите наименьшее число k> = 1 такое, что n + k является простым.

Сформируйте пары: (n, k), (n-1, k + 1), ..., (k , n).

Если k> 1, повторить в диапазоне [1, k].

Например, n = 5: 5 + 2 = 7, поэтому мы имеем:

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

Затем мы повторяем для 1.

Например, n = 8: 8 + 3 = 11, поэтому мы имеем:

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

Оставляя нас с 2:

1, 2
2, 1

Согласно постулату Бертрана, также известному как теорема Чебышева, для любого n> 1 существует простое число p st n

Answer 2

Постройте двудольный граф на {0,1} x {1 ... n} так, чтобы (0, i) и (1, j) были связаны тогда и только тогда, когда i + j простое число.

Найдите идеальное совпадение, используя любую стандартную технику, а затем создайте последовательности так, чтобы совпадающие числа находились в одном индексе.