Project Euler – Problem 71 | Incongruent Thoughts

Analysis

Let $d$ be some integer larger than $1$ , $F(d) = \{ \frac{a}{b} : 1 \leq a < b \leq d\}$ and $F_0(d) = \{0\} \cup F(d)$ . Let $prev_d$ be a function from $F(d)$ to $F_0(d)$ defined as follows:

$prev_d(t) = s$ ,

where $s$ is the largest fraction in $F_0(d)$ that is less than $t$ . As the example in the problem illustrates, $prev_8(\frac{3}{7}) = \frac{2}{5}$ . We need to find $prev_{1000000}(\frac{3}{7}).$

Let $t \in F(d)$ and $n$ be an integer between $1$ and $d$ inclusive. We now define $p_d(t,n)$ as follows:

$p_d(t,n) = s$ ,

where $s$ is the largest fraction with a denominator of $n$ in $F_0(d)$ that is less than $t$ .

Clearly then,

$prev_d(t) = max_{2 \leq n \leq d}\{ p_d(t,n) \}$ .

Thus it suffices to show how to compute $p_d(t,n)$ . The implementation which will be given below uses a modified binary search to compute $p_d(t,n)$ . The running time is $O(lg\,n)$ . Therefore, it takes

$lg\,2 + lg\,3 + \cdots + lg\,d = lg\,d! = O(d \cdot lg\,d)$

time to compute $prev_d(t)$ for any $t$ .

Implementation of $p_d(t,n)$

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 $prev_8(\frac{3}{7})$ .

> (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 $\frac{2}{5}$ is the maximum of the values that were computed, we can conclude that $prev_8(\frac{3}{7}) = \frac{2}{5}$ .

Finally, we use the same idea to get $prev_{1000000}(\frac{3}{7})$ . The full implementation takes about 7 seconds to compute the answer.

About these ads

Incongruent Thoughts

My musings on programming, mathematics and life

Project Euler – Problem 71

Analysis

Implementation of $p_d(t,n)$

Like this:

Leave a Reply Cancel reply

Follow “Incongruent Thoughts”