By replacing the 1st digit of *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.
Analisi:
1) Dal testo si deduce che le cifre da sostituire sono 3 o più.
2) Grazie a Google sappiamo che sostituendo 2 o 4 cifre al numero di 6 cifre,
non raggiungeremo mai una famiglia di 8 primi perchè si avrebbero numeri divisibili
per 3, quindi non primi (almeno 3):
test 2-4 cifre:
def three_divisible(low, hi, qty):
results = []
for n in range(low, hi):
res = []
for d in '0123456789':
num = d * qty + str(n)
a = sum([int(i) for i in str(num)])
if a % 3 == 0:
res.append(n)
if len(res) < 3: # at least 8 primes
results.append(res)
return len(results)
for low, hi, qty in ((10, 99, 4), (1000, 9999, 2)):
print 'length for non 3-divisible list with {} replaced dig : {}'.format(
qty, three_divisible(low, hi, qty))
3) L’ultima cifra deve fare parte del gruppo ‘1379’ per non fare perdere
al numero di 6 cifre, la propria primalità.
Dobbiamo conoscere le varie combinazioni (posizioni) delle cifre da sostituire.
Ci avvaliamo di itertools:
for pattern in it.permutations('abxxx'):
nota:
la cifra c non la contemplo poichè la aggiungerò alla fine, sapendo che è limitata
al gruppo ‘1379’
Essendo le ‘x’ le cifre uguali pescate da ‘0123456789’, non mi rimane che ciclare
su ‘a’ e ‘b’, quindi da 11 a 99.
python:
import time
import itertools as it
ts = time.time()
def is_prime(num):
if num <= 1: return False
elif num == 2: return True
elif num % 2 == 0: return False
else:
d = 3
r = int(num**0.5)
while d <= r:
if num % d == 0: return False
d += 2
return True
def get_subs_primes(n, ptrn):
pattern = ''.join(ptrn)
digits = '0123456789'
values = []
sn = pattern.replace('a', n[0]).replace('b', n[1])
for d in digits:
snr = sn.replace('x', d) + n[2]
if is_prime(int(snr)) and snr[0] != '0': # '0' leading excluded
values.append(int(snr))
return values
results = []
patterns = [''.join(p) for p in it.permutations('abxxx') # pattern combinations
if ''.join(p).find('a') < ''.join(p).find('b')]
for pattern in patterns:
for n in xrange(11, 99): # 'a' and 'b'
for lastd in '1379': # last digit
num = str(n) + lastd
a = get_subs_primes(num, pattern)
if len(a) == 8:
results.append(min(a))
try:
res = min(results)
print "problem euler 51: {} \nelapsed time: {}sec".format(res, time.time() - ts)
except ValueError:
print "No result found"
Commenti recenti