Problem Euler #72
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.
Commenti recenti