Trusted answers to developer questions

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:

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

Related Courses