90 lines
2.7 KiB
Python
90 lines
2.7 KiB
Python
#!/usr/bin/python
|
|
|
|
# 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.
|
|
|
|
from projecteuler import sieve, timing
|
|
|
|
|
|
N = 1000000
|
|
# N set to 1000000 as a reasonable limit, which turns out to be enough.
|
|
primes = sieve(N)
|
|
|
|
|
|
def count_digit(n: int, d: int) -> int:
|
|
count = 0
|
|
|
|
while n > 0:
|
|
if n % 10 == d:
|
|
count = count + 1
|
|
n = n // 10
|
|
|
|
return count
|
|
|
|
|
|
def replace(n: int) -> int:
|
|
n_string = list(str(n))
|
|
l = len(n_string)
|
|
_max = 0
|
|
|
|
for i in range(l-3):
|
|
for j in range(i+1, l-2):
|
|
# Replacing the last digit can't give 8 primes, because at least
|
|
# six of the numbers obtained will be divisible by 2 and/or 5.
|
|
for k in range(j+1, l-1):
|
|
count = 0
|
|
|
|
for w in range(10):
|
|
if i == 0 and w == 0:
|
|
continue
|
|
|
|
n_string = list(str(n))
|
|
n_string[i] = str(w)
|
|
n_string[j] = str(w)
|
|
n_string[k] = str(w)
|
|
|
|
n_replaced = int(''.join(n_string))
|
|
|
|
if primes[n_replaced] == 1:
|
|
if count == 0 and n_replaced != n:
|
|
continue
|
|
|
|
count = count + 1
|
|
|
|
_max = max(_max, count)
|
|
|
|
return _max
|
|
|
|
|
|
@timing
|
|
def p051() -> None:
|
|
# Checking only odd numbers with at least 4 digits.
|
|
i = 1001
|
|
|
|
while i < N:
|
|
# The family of numbers needs to have at least one of 0, 1 or 2 as
|
|
# repeated digits, otherwise we can't get a 8 number family (there
|
|
# are only 7 other digits). Also, te number of repeated digits must
|
|
# be 3, otherwise at least 3 resulting numbers will be divisible by 3.
|
|
# So the smallest number of this family must have three 0s, three 1s or
|
|
# three 2s.
|
|
if count_digit(i, 0) >= 3 or count_digit(i, 1) >= 3 or\
|
|
count_digit(i, 2) >= 3:
|
|
if primes[i] == 1 and replace(i) == 8:
|
|
break
|
|
|
|
i = i + 2
|
|
|
|
print('Project Euler, Problem 51')
|
|
print(f'Answer: {i}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p051()
|