Problem 51 Project Euler Solution with python

Prime digit replacements

By replacing the 1^st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.
By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.
Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

This problem again depends on both mathematics and programming. According to me this problem gives more weight-age for mathematics than for programming.

Okay lets get started. There is one thing which I wanted to explain but, I think it will be better if I will link you to a stack answer where one guy has explained it very nicely.

Alex Becker answer for Primality and repeated digits Stackoverflow

Solution written by Mr.Alex has a lot of algebra and I recommend you take some example number(like 56003/56113/...) and substitute the values in the variables and you'll for sure understand the explanation given in the question.

Algorithm based on which the program has been written can be given in steps as follows:

1) Generate prime numbers upto 1 million, preferably using Sieve of Eratosthenes. I have used the modified sieve algorithm which we have created in Problem 37 Project Euler Solution with python.

2) As per the answer given by Alex, take the list from Step 1(prime numbers list), we will only retain prime numbers, in which we are having three or more repeated digits.(Even though 4 is not required, when I tried using this condition, the program lost its speed.) To be simple we will use only primes that have more than or equal to 3 digits that have been repeated. For example 56663 etc.

3) Create a list checked to store all the checked numbers(Numbers generated in Step 5) in each every iteration.

4) Start iterations and, for each and every prime number, check whether it is not in checked list, and proceed further.

5) Find all the replacements for the given number, if you are given a number 566003, then you should be able to generate

[[566003,566113,566223,566333,566443,566553,566663,566773,566883,566993],[500003,511003,522003,533003,544003,555003,566003,577003,588003,599003]]

6) As you can see we are having nested lists returned from Step 5, so take a list, add all the items to the checked list. Take the list and remove all the non-prime numbers. Now return the modified list(list without prime numbers) to step 7.

7) Take the modified list and check if its length is 8, if the length is 8 then print the first element in the list and break all the loops, if the length is not 8, then start again from Step 5 with the next prime number.

I don't have any explanation for why I have used Sieve with upper bound 1 million, I just have assumed it, this has been done to speed up the program, you can use your own prime generating function to get the solution. There is no need for assuming 1 million if you are not satisfied.

If you have already seen the program, steps which we have discussed above has been directly used in the program in form of functions. Have a look at the program if you haven't yet.

Program

File: pep51.py ------------------------- # http://radiusofcircle.blogspot.com # import counter to find the duplicates from collections import Counter # importing time import time # time at the start of program execution start = time.time() # Sieve of Erotosthenes # One of the best algorithm to generate prime numbers # https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes def sieve(n): is_prime = [True]*n is_prime[0] = False is_prime[1] = False is_prime[2] = True # even numbers except 2 have been eliminated for i in xrange(3, int(n**0.5+1), 2): index = i*2 while index < n: is_prime[index] = False index = index+i prime = [2] for i in xrange(3, n, 2): if is_prime[i]: prime.append(i) return prime # primes upto 1 million primes = sieve(1000000) # primes with 3 replacable places primes = [x for x in primes if len(str(x)) - len(set(str(x))) >= 3] def pdr(s): """take a number and return a list with families for example if the input number is 566003 then the result will be [[566003,566113,566223,566333,566443,566553,566663,566773,566883,566993], [500003,511003,522003,533003,544003,555003,566003,577003,588003,599003]]""" s = str(s) sol = [] for duplicate in (Counter(s) - Counter(set(s))): a = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] temp = [int(s.replace(duplicate, x)) for x in a] sol.append(temp) return sol # list to store all the checked numbers, so not to repeat checked = [] def check(l): """take a list and remove all the values which are not prime numbers, finally return a list with only prime numbers""" for i in l: checked.append(i) if i not in primes: l.remove(i) return l # condition for while loop flag = True # while loop iterator i = 0 # while loop while flag: # check if we have not check the number before if primes[i] not in checked: # find the family of the given number replacements = pdr(primes[i]) for j in replacements: if len(check(j)) == 8: print j[0] flag = False break i += 1 # time at the end of program execution end = time.time() # total time taken for execution print end - start

I have imported the Counter from collections in order to find the duplicates in the given prime numbers. You can see more from Find duplicates words in a text.

sieve function

We have discussed about this function earlier, if you don't know about Sieving then you can have a look at Problem 37 project Euler Solution with python.

len(str(x)) - len(set(str(x))) >= 3

This one is used for checking for duplicates in a given string(here it is number). For example len('56003') = 5, len(set('56003')) = len(set('5','6','0','3')) = 4, so there is one duplicated thing in the given string.

pdr function.

This function is the heart of this question(Prime Digit Replacements), it will take a number and will return the family of the number. This function accomplishes the task stated in Step 5.

checked = []

As discussed in Step 6.

check function.

This function will take a list, add all the items in the list to checked list. It will also delete all non-prime numbers in the list. Finally at the end of all the iterations it will return the list with only prime numbers. As discussed in Step 6.

while flag:

I have used a while loop because I wanted to break out of two loops, after I have found the answer.

All the remaining code has been explained in the algorithm.

You can download the source code from Github Gist pep51.py

Output

Summary

I personally liked this problem because it made me think bigger when compared to previous problems. At first I had execution time of around 10 seconds, but using the condition stated by Alex I have been able to reduce the execution time considerably. One thing I wanted to share is, that using Sieve of Atkins, execution time increased when compared to Sieve of Eratosthenes. I don't know the reason for this kind of behavior. This problem demanded a lot of mathematical approach when compared to programming approach. Anyways what ever it might be, with the help of stack overflow I was able to solve this problem with an optimized program. I am satisfied with the execution time. But one can still improve the program, I am sure that there still is scope for improvement. I myself have found some code block which can be improved, but I am leaving it to you.

Please excuse me and correct me if my grammar in this post is not understandable or is an ambiguous manner.

As always, you can comment in the comment box below if you have any doubt or haven't understood anything. I will be glad to help you.

Please do comment in the comment box below, if you have found a typo or have a better program or have a different program or have a suggestion. I will be very happy to view each of them.

You can also contact me.

Thank you. Have a nice day😃!

RADIUS OF CIRCLE

Search This Blog