Finding Prime Families by Digit Replacement

[Arman777]

Homework Statement

By replacing the 1st 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 3rd and 4th 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.

https://projecteuler.net/problem=51

Homework Equations

The Attempt at a Solution

I am trying to create an algorithm but I am not sure how to approach the problem. It seems really hard. Anyone can show me a tip ?

 

[mfb]

It will need some computing, but you can reduce the brute force effort a bit by thinking about divisibility first - especially divisibility by 3.
Alternatively, just test every number if it is part of such a family.

 

[Arman777]

It will need some computing, but you can reduce the brute force effort a bit by thinking about divisibility first - especially divisibility by 3.
Alternatively, just test every number if it is part of such a family.

I used kind of another approach. I managed to solve the problem. I used the list of prime numbers so I didnt need to check that property

import time
start=time.time()

def prime(N):                         #prime number function
    y = int(pow(N,0.5))
    for i in range (2,y+1):
        if N % i == 0:
            return False
    return True

def meas(N):                          #function that defines the statement of the question
    l=0
    for j in range(1,10):
        p=N.replace("s",str(j))
        if prime(int(p))==True:
            l+=1
    if l==8:
        return TruePrimes=[N for N in range(10001,1000000,2) if prime(N) == True]     #prime numbers up to 1 million

P0=[str(i).replace("0","s",3) for i in Primes if str(i).count("0")==3]
P1=[str(i).replace("1","s",3) for i in Primes if str(i).count("1")==3]
P2=[str(i).replace("2","s",3) for i in Primes if str(i).count("2")==3]
P3=[str(i).replace("3","s",3) for i in Primes if str(i).count("3")==3]
P4=[str(i).replace("4","s",3) for i in Primes if str(i).count("4")==3]
P5=[str(i).replace("5","s",3) for i in Primes if str(i).count("5")==3]
P6=[str(i).replace("6","s",3) for i in Primes if str(i).count("6")==3]
P7=[str(i).replace("7","s",3) for i in Primes if str(i).count("7")==3]
P8=[str(i).replace("8","s",3) for i in Primes if str(i).count("8")==3]
P9=[str(i).replace("9","s",3) for i in Primes if str(i).count("9")==3]

H=[]
Numbers=[P0,P1,P2,P3,P4,P5,P6,P7,P8,P9]
for i in range(10):
    y=Numbers[i]
    for j in range(len(y)):
        H.append(y[j])

L=list(set(i for i in H if H.count(i)>5))
for i in L:
    if meas(i)==True:
        print(i)                        #The answer

end=time.time()
Time=end-start
print("Time to solve",Time)

The main idea is; if the number has some form like 2s8s3 then the numbers 21813,22823,23833 etc has the same form (2s8s3). Hence in general I am counting these forms. To count these form first I need to remove the numbers that has 3 "0" or 3 "5" etc (which all of the P# arrays are like that) then I am turning them into the s forms(turning these 3 "0" to 3"s"). Then I am counting the forms for each element. (The counting limit should be larger then 5 in this case, because if the number has accidently 4 "2" or 4 "some number" then it can never count up to 8 due to the my code structure. Hence I cannot say count only 8 occurrences or etc.)Then I am sending these numbers to "meas" function to check for "solution". In this process we can eliminate the unnecessary numbers which came by counting process. Then I can find the answer. It could be more optimized but I am fine with this..

Edit:I changed my code a bit

 

[mfb]

That is the "test every number" approach. Primes only of course.

Why did you discard numbers with just one or two replacements?
There is a good reason for it - and for the same reason four and five replacements cannot happen, so you are safe below one million.

 

[Arman777]

That is the "test every number" approach. Primes only of course.

Why did you discard numbers with just one or two replacements?
There is a good reason for it - and for the same reason four and five replacements cannot happen, so you are safe below one million.

Yes indeed. I couldn't think any better algorithm. This one seemed fine and solves in 6-7 sec.

Below one million yes 4 and 5 doesn't make much sense since the numbers are already 6 digits its not possible to find 8 prime set from them.
Why not 1 digit replacement. Well with 1 digit replacement we can max achieve 7 prime set I guess. Cause in each 3 change the sum of the digits will be the multiples of 3 so they cannot be prime. For 2 digits I guess its same kind of reason ?

 

[mfb]

Why not 1 digit replacement. Well with 1 digit replacement we can max achieve 7 prime set I guess. Cause in each 3 change the sum of the digits will be the multiples of 3 so they cannot be prime. For 2 digits I guess its same kind of reason ?

Right. If you increase one digit by 1 you increase the number mod 3 by 1. Out of 10 numbers at least 3 have to be divisible by 3, leaving at most 7 that can be prime. If you increase two digits by 1 you reduce the number mod 3 by 1. Same problem - also for 4 and 5 replacements. With 3 replacements (or any other multiple of 3) you don't change the remainder, that way more primes are possible.