Home > Project Euler, python > Project Euler #72

Project 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

>>> euler_72(5)
5

Come funziona?

A. viene creata la lista phi

>>> phi = range(5)
>>> phi
[0, 1, 2, 3, 4]
>>> 

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

phi[j] = phi[j](1 - 1.0/i)

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

phi[j] = phi[j](1 - 1.0/i)

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
  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: