Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
puzzle

What are prime digit replacements?

Rukhshan Haroon

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:

%0 node_1625165840463 17 node_1625165812592 37 node_1 47 node_1625165870874 67 node_1625165913303 97
Prime number family of 17.

The replacements need not be performed on adjacent indexes. For example, prime digit replacements may be performed on the 0th, 2nd, and 4th indexes of 51121. However, the indexes remain the same for one family.

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()


Solution implemented using Python3.

RELATED TAGS

python
puzzle

CONTRIBUTOR

Rukhshan Haroon
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring