Count of permutations of first N positive integers such that sum of any two consecutive numbers is prime
Find the number of permutations of first N positive integers such that the sum of any two consecutive numbers is prime where all the cyclic permutations are considered the same.
Note: The sum of the first and last element must be prime as well.
Example:
Input: N = 6
Output: 2
Explanation: The two valid permutations are {1, 4, 3, 2, 5, 6} and {1, 6, 5, 2, 3, 4}. The permutation like {3, 2, 5, 6, 1, 4} is considered a cyclic permutation of the 1st one and hence not included.Input: N = 3
Output: 0
Explanation: No valid permutations exist.
Approach: The given problem can be solved by using recursion and backtracking. It can be observed that to find the distinct number of cycles, without loss of generality, the cycle should start with 1. An isPrime[] array can be created using the Sieve of Eratosthenes which stores whether a number is prime or not. Therefore, create a recursive function and add elements in the permutation such that its sum with the last element is prime. Increment the permutation count if the sum of the first and last element is also prime.
Below is the implementation of the above approach:
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Initialize a global variable N
const int maxn = 100;
// Stores the final count of permutations
ll ans = 0;
// Stores whether the integer is prime
bool isPrime[maxn];
bool marked[maxn];
void SieveOfEratosthenes(int n)
{
memset(isPrime, true, sizeof(isPrime));
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
void countCycles(int m, int n, int prev, int par)
{
// If a complete permutation is formed
if (!m) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (int i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
int countPermutations(int N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initializing all values in marked as 0
memset(marked, false, sizeof(marked));
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
int main()
{
int N = 6;
cout << countPermutations(N);
return 0;
}
// Java implementation for the above approach
import java.util.*;
class GFG{
// Initialize a global variable N
static int maxn = 100;
// Stores the final count of permutations
static int ans = 0;
// Stores whether the integer is prime
static boolean []isPrime = new boolean[maxn];
static boolean []marked = new boolean[maxn];
static void SieveOfEratosthenes(int n)
{
for (int i = 0; i <isPrime.length; i += 1) {
isPrime[i]=true;
}
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
static void countCycles(int m, int n, int prev, int par)
{
// If a complete permutation is formed
if (m==0) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (int i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
static int countPermutations(int N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initializing all values in marked as 0
for (int i = 0; i <marked.length; i += 1) {
marked[i]=false;
}
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 6;
System.out.print(countPermutations(N));
}
}
// This code is contributed by 29AjayKumar
# python implementation for the above approach
import math
# Initialize a global variable N
maxn = 100
# Stores the final count of permutations
ans = 0
# Stores whether the integer is prime
isPrime = [True for _ in range(maxn)]
marked = [False for _ in range(maxn)]
def SieveOfEratosthenes(n):
global ans
global isPrime
global marked
for p in range(2, int(math.sqrt(n))+1):
# If prime[p] is not changed,
# then it is a prime
if (isPrime[p] == True):
# Update all multiples of P
for i in range(p*p, n+1, p):
isPrime[i] = False
# Function to find the number of valid permutations
def countCycles(m, n, prev, par):
global ans
global isPrime
global marked
# If a complete permutation is formed
if (not m):
if (isPrime[prev + 1]):
# If the sum of 1st and last element
# of the current permutation is prime
ans += 1
return
# Iterate from par to N
for i in range(1+par, n+1):
if (not marked[i] and isPrime[i + prev]):
# Visit the current number
marked[i] = True
# Recursive Call
countCycles(m - 1, n, i, 1 - par)
# Backtrack
marked[i] = False
def countPermutations(N):
global ans
global isPrime
global marked
# Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N)
# Initial condition
marked[1] = True
countCycles(N - 1, N, 1, 1)
# Return Answer
return ans
# Driver code
if __name__ == "__main__":
N = 6
print(countPermutations(N))
# This code is contributed by rakeshsahni
// C# implementation for the above approach
using System;
public class GFG
{
// Initialize a global variable N
static int maxn = 100;
// Stores the final count of permutations
static int ans = 0;
// Stores whether the integer is prime
static bool []isPrime = new bool[maxn];
static bool []marked = new bool[maxn];
static void SieveOfEratosthenes(int n)
{
for (int i = 0; i < isPrime.Length; i += 1) {
isPrime[i] = true;
}
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
static void countCycles(int m, int n, int prev, int par)
{
// If a complete permutation is formed
if (m==0) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (int i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
static int countPermutations(int N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initializing all values in marked as 0
for (int i = 0; i <marked.Length; i += 1) {
marked[i] = false;
}
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
public static void Main(string[] args)
{
int N = 6;
Console.WriteLine(countPermutations(N));
}
}
// This code is contributed by AnkThon
<script>
// Javascript implementation for the above approach
// Initialize a global variable N
const maxn = 100;
// Stores the final count of permutations
let ans = 0;
// Stores whether the integer is prime
let isPrime = new Array(maxn).fill(true);
let marked = new Array(maxn).fill(false);
function SieveOfEratosthenes(n) {
for (let p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (isPrime[p] == true) {
// Update all multiples of P
for (let i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Function to find the number of valid permutations
function countCycles(m, n, prev, par) {
// If a complete permutation is formed
if (!m) {
if (isPrime[prev + 1]) {
// If the sum of 1st and last element
// of the current permutation is prime
ans++;
}
return;
}
// Iterate from par to N
for (let i = 1 + par; i <= n; i++) {
if (!marked[i] && isPrime[i + prev]) {
// Visit the current number
marked[i] = true;
// Recursive Call
countCycles(m - 1, n, i, 1 - par);
// Backtrack
marked[i] = false;
}
}
}
function countPermutations(N)
{
// Finding all prime numbers upto 2 * N
SieveOfEratosthenes(2 * N);
// Initial condition
marked[1] = true;
countCycles(N - 1, N, 1, 1);
// Return Answer
return ans;
}
// Driver code
let N = 6;
document.write(countPermutations(N));
// This code is contributed by gfgking.
</script>
Output
2
Time Complexity: O(N!)
Auxiliary Space: O(N)
Efficient Approach Using Dynamic Programming and Bitmasking
To count permutations of the first N positive integers such that the sum of any two consecutive numbers is prime, we can use dynamic programming combined with bitmasking. This approach reduces the problem’s complexity significantly by efficiently storing and reusing intermediate results.
Approach:
- Use a bitmask to represent the subset of integers that have been included in the permutation so far.
- Use dynamic programming to store the number of valid permutations that can be formed starting from each integer.
- Precompute the prime sums for quick lookup.
- Ensure that the permutation cycle is valid by checking the sum of the first and last elements.
#include <iostream>
#include <vector>
#include <set>
#include <cmath>
using namespace std;
// Function to check if a number is prime
bool isPrime(int num) {
if (num <= 1) return false;
if (num <= 3) return true;
if (num % 2 == 0 || num % 3 == 0) return false;
for (int i = 5; i * i <= num; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) return false;
}
return true;
}
int countPermutations(int N) {
// Precompute prime sums
set<int> primes;
for (int i = 2; i <= 2 * N; ++i) {
if (isPrime(i)) {
primes.insert(i);
}
}
// DP array to store the number of valid permutations ending at each integer
vector<vector<int>> dp(1 << N, vector<int>(N, 0));
dp[1][0] = 1; // Starting with 1
// Iterate over all subsets of integers using bitmasks
for (int mask = 1; mask < (1 << N); ++mask) {
for (int i = 0; i < N; ++i) {
if (!(mask & (1 << i))) continue;
for (int j = 0; j < N; ++j) {
if (mask & (1 << j) || primes.find(i + 1 + j + 1) == primes.end()) continue;
dp[mask | (1 << j)][j] += dp[mask][i];
}
}
}
// Sum up all valid permutations that form a cycle
int result = 0;
int full_mask = (1 << N) - 1;
for (int i = 1; i < N; ++i) {
if (primes.find(i + 1 + 1) != primes.end()) {
result += dp[full_mask][i];
}
}
return result;
}
// Driver code
int main() {
int N = 6;
cout << countPermutations(N) << endl;
return 0;
}
import math
# Function to check if a number is prime
def is_prime(num):
if num <= 1:
return False
if num <= 3:
return True
if num % 2 == 0 or num % 3 == 0:
return False
i = 5
while i * i <= num:
if num % i == 0 or num % (i + 2) == 0:
return False
i += 6
return True
def count_permutations(N):
# Precompute prime sums
primes = set()
for i in range(2 * N + 1):
if is_prime(i):
primes.add(i)
# DP array to store the number of valid permutations ending at each integer
dp = [[0] * N for _ in range(1 << N)]
dp[1][0] = 1 # Starting with 1
# Iterate over all subsets of integers using bitmasks
for mask in range(1 << N):
for i in range(N):
if not (mask & (1 << i)):
continue
for j in range(N):
if mask & (1 << j) or (i + 1 + j + 1) not in primes:
continue
dp[mask | (1 << j)][j] += dp[mask][i]
# Sum up all valid permutations that form a cycle
result = 0
full_mask = (1 << N) - 1
for i in range(1, N):
if (i + 1 + 1) in primes:
result += dp[full_mask][i]
return result
# Driver code
N = 6
print(count_permutations(N))
Output
2
Time Complexity: O(N * 2^N)
Space Complexity: O(N * 2^N)
Contact Us