Home > Project Euler, python > Problem Euler #72

Problem Euler #72

26 Febbraio 2013
Consider the fraction, n/d, where n and d are positive integers.
If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d <= 8 in
ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5,
5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 21 elements in this set.
How many elements would be contained in the set of reduced proper
fractions for d <= 1,000,000?

Analisi:

Come facciamo a determinare il numero di frazioni proprie ridotte di un numero?
Una frazione propria ridotta è quella frazione che ha il numeratore minore del denominatore
(propria) e con gcd (massimo comune denominatore) = 1.
Significa anche che numeratore e denominatore sono relativamente primi.
Quindi, dato un numero ‘i’, tutti i numeratori relativamente primi ad ‘i’ e minori di ‘i’, con
‘i’ al denominatore, sono frazioni proprie ridotte.
Per calcolare il numero di interi compresi tra 1 ed ‘i’ che sono coprimi con ‘i’, si usa
la funzione di Eulero.
La formula che ci interessa è:

phi(i) = i * [(1 - 1/p1) * (1 - 1/p2) ...]

Un approccio Brute Force purtroppo sfora dal minuto richiesto, quindi
utilizzeremo un algoritmo simile al crivello di eratostene.
Iteriamo cioè sun una lista contenente tutti i numeri da 2 al limite
richiesto; quando il valore contenuto in quell’indice di lista è uguale
al valore dell’indice stesso, allora iteriamo nuovamente su tutti i valori
compresi tra quel numero ed il limite (con passo pari al numero stesso, in modo
che phi venga calcolata solo sui divisori del numero stesso).

questo è il codice:

import time

st = time.time()

def euler_72(limit):
    phi = range(limit)
    for i in xrange(2, limit):
        if phi[i] == i: # sieve
            for j in xrange(i, limit, i):
                phi[j] *= 1 - 1.0/i
    return int(sum(phi) - 1)


print "Project Euler 72: {}".format(euler_72(10**6 + 1))
print "elapsed time: {}sec".format(time.time() - st)

Spiegazione:

partiamo con un esempio facile.
Cerchiamo il numero di frazioni proprie ridotte per n <= 4. Sappiamo che: phi(2) = 1 phi(3) = 2 (i primi hanno risultato p-1) phi(4) = 2 quindi la funzione deve dare come risultato 5 [sourcecode lang="text"] >>> euler_72(5) 5[/sourcecode] Come funziona? A. viene creata la lista phi [sourcecode lang="text"] >>> phi = range(5) >>> phi [0, 1, 2, 3, 4] >>> [/sourcecode] B. si itera sui numeri da 2 a 4 compreso quando phi[i] = i entra in azione il crivello. il primo numero è ovviamente 2, siccome phi[2] = 2, iniziamo con il secondo for-loop che itererà su numeri da 2 a 4 compreso, con step 2, quindi 2 e 4. al primo giro abbiamo che [sourcecode lang="text"]phi[j] = phi[j](1 - 1.0/i)[/sourcecode] siccome j=2, abbiamo che phi[2] = 2 quindi phi[2] = 2 * (1 - 1/2) = 1 in questo modo phi[2] = 1 (non più 2) ora al secondo giro avremo j=4 [sourcecode lang="text"]phi[j] = phi[j](1 - 1.0/i)[/sourcecode] phi[4] = 4 quindi phi[4] = 4 * (1 - 1/2) = 2 ora anche phi[4] ha cambiato il proprio valore. Finito il loop annidato, torniamo a quello esterno e da i = 2, passiamo ad i = 3 phi[3] non è stato ancora toccato infatti phi[3]=3 entriamo nel secondo loop dove itereremo da 3 a 5 con step = 3, quindi solo un "giro" (3). phi[3] = 3 quindi phi[3] = 3 * (1 - 1/3) = 2 usciamo dal loop annidato e torniamo in quello esterno: i = 4 phi[4] != 4 perchè modificato dal loop annidato durante il primo ciclo, quindi non succede nulla. La lista modificata sarà: [0, 1, 1.0, 2.0, 2.0] Ora basterà restituire la somma di tali valori, escluso il secondo (phi(1) = 1) che non ci interessa.

Categorie:Project Euler, python Tag:
I commenti sono chiusi.