The problem: Problem 71
Let be some integer larger than , and . Let be a function from to defined as follows:
where is the largest fraction in that is less than . As the example in the problem illustrates, . We need to find
Let and be an integer between and inclusive. We now define as follows:
where is the largest fraction with a denominator of in that is less than .
Thus it suffices to show how to compute . The implementation which will be given below uses a modified binary search to compute . The running time is . Therefore, it takes
time to compute for any .
Uses the racket programming language.
;; finds the largest fraction with a denominator of n ;; that is less than t (define (p t n) ;; assumes n <= d (let ([a (numerator t)] [b (denominator t)]) (/ (let loop ([l 0] [h (- n 1)]) (if (> l h) 0 (let ([m (quotient (+ l h) 2)]) (if (< (* m b) (* a n)) (max m (loop (+ m 1) h)) (loop l (- m 1)))))) n)))
An example showing how to use p to compute .
> (p (/ 3 7) 2) 0 > (p (/ 3 7) 3) 1/3 > (p (/ 3 7) 4) 1/4 > (p (/ 3 7) 5) 2/5 > (p (/ 3 7) 6) 1/3 > (p (/ 3 7) 7) 2/7 > (p (/ 3 7) 8) 3/8
Since is the maximum of the values that were computed, we can conclude that .
Finally, we use the same idea to get . The full implementation takes about 7 seconds to compute the answer.