**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:

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.

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.

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 mathfrom itertools import combinations#prime number generator, implements the Sieve of Eratosthenes algorithmdef 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 familydef calculate(n,k,l):length = int("9"*n)prime_numbers = generate_prime(length)#removes all numbers of length smaller than nprime_numbers[:] = (value for value in prime_numbers if len(value) == n)no_primes = 0temp = []#removes all numbers that have less than k repeated digitsprime_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 replacementcombinations = combo_maker(n,k)comp = 0check = True#loop to separate the results of a prime digit replacement performed in a given combinationfor 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 = Falseif check == True:temp.append(j)check = True#call to separatorresults = 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 Ldef separator(i, numbers, k, l,n):record = []secondary = []check = Trueconcat = ""#loop to single out prime digit familiesfor 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 Lfor 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=kdef 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 combdef main():calculate(5, 2, 7)main()

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS