Non‐Prime Sum Permutation

Given a positive integer \( n \), construct a permutation \( p \) of the set \(\{1,2,\ldots,n\}\) such that for every two consecutive elements \( p_i \) and \( p_{i+1} \), the sum \( p_i+p_{i+1} \) is not a prime number (i.e. it is composite). In other words, for all \( 1 \le i < n \), \( p_i+p_{i+1} \) should be composite. If there is no valid permutation satisfying this property, output -1.

Note: For example, when \( n=1 \), the only permutation is [1]. It has no adjacent pairs so it is valid. For some small values like \( n=2,3,4 \) it can be proven that no permutation exists, and hence the correct output is -1. For \( n \ge 5 \), a valid permutation always exists.

The solution requires the use of LaTeX for any mathematical formulas.

inputFormat

The input consists of a single integer \( n \) provided via standard input.

outputFormat

If a valid permutation exists, output the permutation as a sequence of \( n \) space-separated integers on a single line to standard output. Otherwise, output -1.

1

1