bancaldo™

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 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 12,000?

Analisi:

Con un approccio Brute Force si sfora sicuramente dal minuto limite.
Utilizzando la sequenza di Farey, si ottimizza e non poco, il tempo
di esecuzione.
Date due frazioni adiacenti a/b e c/d, la formula che ci interessa per calcolare la successiva frazione e/f è:

e = int((n + b) / d) * c - a
f = int((n + b) / d) * d - b

Avendo come punto di partenza 1/3, considerando n = 12000, dobbiamo
trovare la frazione adiacente ad 1/3. Ci viene in soccorso dal link precedente, la seconda formula che dice che:
due frazioni a/b e c/d sono adiacenti se:

b * c – a * d = 1

in questo caso 1/3 e 4000/11999

Fatto questo, con un normale while-loop continueremo a calcolare le successive frazioni adiacenti fino a che il risultato non sarà 1/2.

python:

import time

START = time.time()

def farey(n):
    a, b, c, d = 1, 3, 4000, 11999
    res = 0
 
    while c != 1 and d != 2:
        res += 1
        k = int((n + b) / d)
        e = k * c - a;
        f = k * d - b;
        a, b = c, d
        c, d = e, f
    return res
            
print farey(12000)
print time.time() - START