Home > Project Euler, python > Project euler #57

Project euler #57

It is possible to show that the square root of two can be expressed
as an infinite continued fraction.

sqrt( 2 ) = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408,
but the eighth expansion, 1393/985, is the first example where the number
of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a
numerator with more digits than denominator?

Analisi:
partendo dalla prima iterazione del testo, si nota che la frazione successiva, sarà sempre così composta:
nuovo denominatore = vecchio numeratore + vecchio denominatore
nuovo numeratore = nuovo denominatore + vecchio denominatore

rapido ed indolore

python:

import time

ts = time.time()
num, den = 3, 2
count  = 0

i = 1
while i < 1000:
    newden = num + den
    num, den = newden + den, newden
    if len(str(num)) > len(str(den)):
        count += 1
    i += 1

print "problem euler 57: {}\nelapsed time: {}".format(count, time.time() - 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: