Count the permutations of first N positive integers such that the sum of any two consecutive numbers is prime

Introduction

Let us discuss the problem statement. We are given an integer N. We need to count the permutations of first N positive integers such that the sum of any two consecutive numbers in the permutation is a prime number. Also, the sum of the first and the last number in the permutation should be prime. All cyclic permutations are counted as one. 

Also read, permutation of string

Input

N = 4

Output

2

Explanation

The two valid permutations following the given constraints are: {1, 4, 3, 2} and {1, 2, 3, 4}. Note that the sum of any two consecutive numbers is a prime. Also, the first and last number adds up to a prime number. 

{1, 2, 3, 4}., {4, 1, 2, 3}, {3, 4, 1, 2} etc… are all counted as one because they are cyclic permutations of one another.  Hence, the count the permutations of first N positive integers following all the constraints is 2. 

Input

N = 5 

Output

0

Explanation:

There are no such permutations that follow the given constraints. 

Input

8

Output

4

Explanation

The permutations following the given constraints are:

1 2 3 8 5 6 7 4 

1 2 5 8 3 4 7 6 

1 4 7 6 5 8 3 2 

1 6 7 4 3 8 5 2 

Hence, the count the permutations of first N positive integers, where N = 8, following all the constraints is 4.

Solution Approach 

Idea

We will use recursion and backtracking to solve the problem of Count the permutations of first N positive integers. We will build every possible permutation recursively. While building a permutation, we ensure that all the constraints provided are followed. Since all the cyclic permutations are counted as one, we need not build all of them. To achieve this, we fix the first number in the permutation as one (it could be any number in the range [1, N], but it should be the same for all permutations). 

Algorithm

1. We declare two arrays, ‘isPrime[]’ and ‘taken[]’. ‘isPrime[]’ is a boolean array that gives information about whether a number is prime or not. isPrime[i] = true, means i is a prime number. taken[] is also a boolean array. It provides information about whether a number is used in the permutation or not. taken[i] = true, means i is part of the current permutation that is being built by the algorithm.  
2. We define a wrapper function ‘countPerm(int N)’. The function definition goes like this: 
   1. We set the size of isPrime[] to 2N because we are working with numbers in the range [1, N], the maximum sum of any two consecutive numbers in a permutation is (N) + (N - 1) = 2N - 1. Therefore the size of the isPrime[] array is 2N.
   2. Call the simpleSieve() method. ‘simpleSieve()’ updates isPrime[i] (0 <= i < 2N) as true/false based on the fact that i is prime or not. 
   3. Reset the size of ‘taken[]’ to ‘N+1’. 
   4. Declare an empty array ‘perm[]’ that holds the current permutation. Push 1 into perm[] and mark taken[1] = true. 
   5. Set ANS = 0. This stores the answer.
   6. Call ‘countPermHelper(N, ANS, perm[])’. This function executes the logic(recursion + backtracking). 
   7. Print ‘ANS’. 
3. We define ‘countPermHelper(N, ANS, perm[])’ as:
   1. Initialize IDX = size of perm[]. ‘IDX’ is the index where we want to place a number. 
   2. Check for the base case. If IDX = N, increment ‘ANS’ as ANS = ANS + 1 and return. When IDX = N, it means that no number in [1, N] is left to be put in the permutation. 
   3. Run a loop from i = 2 to N, push ‘i’ into the perm[] if it is not used in the permutation i.e taken[i] = false and i + immediate previous number in the permutation is a prime number i.e. isPrime[i + perm[IDX - 1]] = true. There is one edge case to handle. When IDX = N - 1, when ‘IDX’ points to the last space in the perm[] array, check if i + 1 is prime or not. Because one of the constraints is the sum of the first and the last number in the permutation must also be a prime. 
   4. Make a recursive call to ‘countPermHelper(N, ANS, perm[])’ to build a valid permutation. 

Note: In the implementation, we have used perm.back() which is equivalent to perm[IDX-1].

C++ Code implementation

Output 

Complexity Analysis

Time complexity: O(N!)

Time Complexity of Count the permutations of first N positive integers in O(N!). As, we are essentially trying to form every permutation and check if it follows the given constraints. From basic permutations and combinations, we know that the number of ways to arrange N objects is N!. Technically, it is (N - 1) for the above solution since we are fixing the first number to 1. Therefore the overall time complexity is O(N!).

Space complexity: O(1)

Space Complexity for Count the permutations of first N positive integers is O(1). If we ignore the space used by the recursion call stack, we are not using any auxiliary space. Therefore, the space complexity is O(1). 

Also see, Euclid GCD Algorithm