What are prime digit replacements?

Prime digit replacement is replacing the value of certain indexes in a prime number to obtain a new prime number.

We define a prime number family as a sequence of prime numbers obtained via prime digit replacements. Each index can hold any value from 0 to 9.

For this problem, we do not consider trailing zeroes. Hence, the index 0 must not contain 1.

For example, 17 is a prime number, and 1 is stored at its 0th index. Performing prime digit replacements at index 0 will result in the following prime numbers:

Problem

Write a program that finds all possible prime digit families consisting (in total) of L prime numbers, each of length N, with K number of prime digit replacements.

Your solution must obey the following constraints:

N must be greater than or equal to 2 and smaller than or equal 7.
K must be greater than or equal to 1 and smaller than or equal to N.
L must be greater than or equal to 1 and smaller than or equal to 8.

Solution

We define a function named generate prime to generate prime numbers up to the largest possible number of length N.

The calculate function first removes those numbers of a length less than N. Subsequently, it further removes those numbers which have less than K repeated digits. This is to ensure that the number of prime digit replacements is equal to K.

The resulting list of prime numbers is sent as input to separator, which creates masks for all possible index combinations in which a prime digit replacement may be performed. The combinations are sent to the separator function iteratively.

If the resulting family of prime numbers is of a length equal to L, it is returned and printed onto the screen. We can see this as follows:

import math
from itertools import combinations
#prime number generator, implements the Sieve of Eratosthenes algorithm
def generate_prime(n): 
	prime_numbers = []
	for i in range(2, n+1, 1):
		prime_numbers.append(int(i))
	limit = int(math.sqrt(n))
	for i in range(2,limit+1, 1):
		for j in range(0,len(prime_numbers)):
			if prime_numbers[j]!= "%":
				if prime_numbers[j]%i == 0:
					prime_numbers[j] = str("%")
	prime_numbers[:] = (value for value in prime_numbers if value != "%")
	for i in range(len(prime_numbers)):
		prime_numbers[i] = str(prime_numbers[i])
	return prime_numbers
#n is the length of the number
#k is the number of replacements
#l is number of primes in that family
def calculate(n,k,l):
	length = int("9"*n)
	prime_numbers = generate_prime(length)
	#removes all numbers of length smaller than n
	prime_numbers[:] = (value for value in prime_numbers if len(value) == n) 
	no_primes = 0
	temp = []
	#removes all numbers that have less than k repeated digits
	prime_numbers[:] = (value for value in prime_numbers if (value.count(str(0)) >= k or value.count(str(1)) >= k or value.count(str(2)) >= k or value.count(str(3)) >= k or value.count(str(4)) >= k or value.count(str(5)) >= k or value.count(str(6)) >= k or value.count(str(7)) >= k or value.count(str(8)) >= k or value.count(str(9)) >= k ))
	#computes all possible combinations to perform a prime digit replacement 
	combinations = combo_maker(n,k)
	comp = 0
	check = True
	#loop to separate the results of a prime digit replacement performed in a given combination
	for i in combinations:
		for j in prime_numbers:
			for f in range(k):
				if f == 0:
					comp = str(j[i[f]])
				elif comp != str(j[i[f]]):
					check = False	
			if check == True:
				temp.append(j)
			check = True
		#call to separator
		results = separator(i, temp, k,l,n)
		if len(results) > 0:
			print(results)
		temp =[]
#function to single out prime digit families, and determine if a particular family is of size L
def separator(i, numbers, k, l,n):
	record = []
	secondary = []
	check = True
	concat = ""
	#loop to single out prime digit families
	for index in range(len(numbers)):
		temp = list(numbers[index])
		for index2 in range(n):
			if index2 not in i:
				concat = concat+temp[index2]
		record.append(concat)
		concat = ""
	#loop to check if a particular family is of size L
	for r in range(len(record)):
		if record.count(record[r]) == l:
			secondary.append(int(numbers[r]))
	return secondary
#creates different combinations. It is identical to nCr where n=n and r=k
def combo_maker(n, k):
	input_list = list(range(n))
	comb = list(combinations(input_list, k))
	for i in range(len((comb))):
		comb[i] = list(comb[i])
	return comb
def main():
	calculate(5, 2, 7)
	
main()

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments