Home > Project Euler, python > Project euler #51

Project euler #51

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"


Categorie:Project Euler, python
  1. marzo 7, 2013 alle 6:47 pm

    An interesting discussion is definitely worth comment.
    There’s no doubt that that you ought to publish more about this topic, it might not be a taboo subject but typically people don’t speak about
    these issues. To the next! Cheers!!

  2. settembre 11, 2014 alle 12:12 pm

    I savor, result in I found exactly what I was taking a look for.
    You have ended my four day long hunt! God Bless you man. Have a nice day.
    Bye

  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: