Project Euler Question 51

  • Thread starter Arman777
  • Start date
  • #1
1,904
147

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 ?
 

Answers and Replies

  • #2
35,248
11,501
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.
 
  • #3
1,904
147
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

Python:
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 True


Primes=[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
 
Last edited:
  • #4
35,248
11,501
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.
 
  • #5
1,904
147
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 couldnt think any better algorithm. This one seemed fine and solves in 6-7 sec.

Below one million yes 4 and 5 doesnt 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 ?
 
  • #6
35,248
11,501
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.
 
  • Like
Likes Arman777

Related Threads on Project Euler Question 51

  • Last Post
4
Replies
80
Views
5K
  • Last Post
Replies
5
Views
3K
  • Last Post
2
Replies
27
Views
1K
Replies
0
Views
6K
  • Last Post
Replies
1
Views
671
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
1
Views
9K
  • Last Post
Replies
1
Views
683
Top