Home > Project Euler, python > Problem Euler #26

Problem Euler #26

Per la risoluzione del problema 26:

A unit fraction contains 1 in the numerator.
The decimal representation of the unit fractions with
denominators 2 to 10 are given:

    1/2	= 	0.5
    1/3	= 	0.(3)
    1/4	= 	0.25
    1/5	= 	0.2
    1/6	= 	0.1(6)
    1/7	= 	0.(142857)
    1/8	= 	0.125
    1/9	= 	0.(1)
    1/10	= 	0.1

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle.
It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which 1/d contains the longest recurring
cycle in its decimal fraction part.

ho preso spunto da qui e da qui per il pattern della regex.
Dalla prima analisi, prendiamo per buono il fatto di testare solo i numeri primi, quantomeno i dispari, così da allontanarci dal puro BruteForce, dalla seconda prendo come oro colato la regex.

python:

from decimal import Decimal, getcontext
import re
import time

ts = time.clock()
getcontext().prec = 2000
PATTERN = r'0\.\d*(\d{7,}?)\1+\d*'


def main():
    length = 0
    d = 0
    for n in range(1, 1000, 2):
        match = re.search(PATTERN, str(1/Decimal(n)))
        try:
            l = len(match.group(1))
            if l > length:
                length = l
                d = n
        except AttributeError:
            pass
    return d

if __name__ == '__main__':
    print main()
    print time.clock() - ts

Note sul pattern:

0\.\d*(\d{7,}?)\1+\d*

Vediamo sezione per sezione

0\.

Tutti i risultati da 1/2 a 1/1000 cominciano con ‘0.’, quindi qui matchiamo lo ‘0’ ed il ‘.’. Ecco spiegato l’escape (\.)

\d*

Qui matchiamo tutti i numeri decimali (\d). Il simbolo ‘*’ indica ‘zero o più volte. A noi interessano le parti ripetibili, ma potrebbe essere che il primo decimale (o più) non ci interessino, come nel caso di 1/6.
Tale frazione dà come risultato 0.166666… Quindi la prima cifra dopo il ‘.’ non ci interessa perchè non fa parte dei ripetitivi.

(\d{7,}?)

Le parentesi ed il loro contenuto, sono il fulcro della regex. La sintassi ‘\d’ già la conosciamo (cerchiamo tutti i numeri).
Considerato l’esempio del testo, contenente 6 digit ripetuti (1/7), partiamo almeno da 7 nella nostra ricerca.
Quindi la sintassi ‘{7,}’ indica che il gruppo che cerchiamo deve avere almeno 7 digit (da 7 in su mettendo la ‘,’).
Il ‘?’ significa che il numero trovato si deve ripetere zero o una volta.

\1+

‘\1’ è un back reference al raggruppamento precedente. Se ci fossero parti multiple con più parentesi ( ) dovremmo arretrare rispettivamente utilizzando \2, \3 etc. Il ‘+’ significa 1 o più volte, perchè vogliamo che il gruppone si ripeta almeno 1 volta.

\d*

Il ‘\d’ finale serve per matchare l’ultima cifra arrotondata, dovuta ai decimali periodici es. 1.6666666… che diventa 1.66666667.
Il ‘*’ significa 0 o 1 ripetizioni del precedente gruppo, nel nostro caso la cifra arrotondata.

Per pizzicare solo i numeri primi e ridurre i tempi di esecuzione:

from decimal import Decimal, getcontext
import re
import time

ts = time.clock()
getcontext().prec = 2000
PATTERN = r'0\.\d*(\d{7,}?)\1+\d*'

def is_prime(num):
    for i in xrange(2, num):
        if num % i == 0:
            return False
    return True

def prime_list(limit):
    for n in xrange(2, limit):
        if is_prime(n):
            yield n

def main():
    length = 0
    d = 0
    for n in prime_list(1000):
        if is_prime(n):
            match = re.search(PATTERN, str(1/Decimal(n)))
            try:
                l = len(match.group(1))
                if l > length:
                    length = l
                    d = n
            except AttributeError:
                pass
    return d

if __name__ == '__main__':
    print main()
    print time.clock() - ts
Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  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: