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

Q: What is Count of permutations of first N positive integers such that sum of any two consecutive numbers is prime?

In this article, we will learn Count of permutations of first N positive integers such that sum of any two consecutive numbers is prime,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Permutation of numbers such that sum of two consecutive numbers is a perfect square

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++

// 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

// 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

# 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

Javascript

<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

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.

C++

#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;
}

Python

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

Time Complexity: O(N * 2^N)

Space Complexity: O(N * 2^N)

Tags:

#permutation #Prime Number #Backtracking #Combinatorial #DSA #Mathematical #Searching #Backtracking #Combinatorial #Mathematical #permutation #Prime Number #Searching

Permutation of numbers such that sum of two consecutive numbers is a perfect square