Close to the root

Almost all other solutions that were presented used the theory of Continued Fractions. There is slight mystery in it, for those who have not seen it before. In this solution, I present another method, using the idea of a Farey sequence:

A Farey sequence of order $n$ refers to an increasing sequence of reduced rational numbers between 0 and 1, whose denominator is a positive integer that is at most $n$ . For example, the Farey sequence of order 5 is:

$\frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{ 2}{5} , \frac 1 2 \frac 3 5 \frac 2 3 \frac 3 4 \frac 4 5 \frac 1 1.$

Now, we'd use a fact about the Farey sequence - consecutive terms are of the form $\frac{a}{b} < \frac{c}{d}$ where $ad-bc = -1$ (Prove this!). Since $\frac{29}{70} > \frac{41}{99}$ and $29\times 99 - 41\times 70 = 1$ , hence these terms are consecutive.

We can also show that $\frac{ 99}{70 }> \sqrt{2} > \frac{140}{99}$ , which tell us that one of these rational numbers must be the best approximation. It remains to compare these two, and we can show that $\frac{99}{70} - \sqrt{2} > \sqrt{2} - \frac{140}{99}$ . Hence, this shows that $\frac{140}{99}$ is the best approximation to $\sqrt{2}$ , hence the answer is 99).

Note: Of course, this doesn't really explain where we got these terms from, apart from being very lucky in guessing.

Using the continued fraction to calculate $\sqrt{2}$ , the last value that has a denominator less than $120$ is $\frac{99}{70}$ .

However, we can get even more precise than this. Since $\sqrt{2} = \frac {2}{\sqrt{2}}$ we can substitute with $\frac{99}{70}$ to get $\frac{99}{70} = \frac{140}{99}$ Using this method further gets us back to $\frac{99}{70}$ so it is no use to work with this method anymore. In addition, since the next value for the continued fraction has a denominator above $120$ , we can stop here and say that $\frac{140}{99}$ is the closest approximation.

If $p / q$ is a best upper approximation to $x$ , then:

1. $p / q \ge x$
2. If there exists $(r, s)$ with $p / q > r / s \ge x$ , then $s > q$ .

If $p / q$ is a best lower approximation to $x$ , then:

1. $x \ge p / q$
2. If there exists $(r, s)$ with $x \ge r / s > p / q$ then $s > q$ .

A rational number is a best upper or lower approximation of $x$ iff it is a convergent or semi-convergent of its continued fraction. Using the continued fraction approximation of $\sqrt{2}$ (that is, $[1; 2 \ldots ]$ ), we find that the under-approximation $140/99$ is the best with $99 < 120$ .

We can use the continued fraction expansion and the solution is straightforward.

Alternatively, we use Farey series to estimate $\sqrt{2} -1$ . From the property of Farey series if $\frac{a}{b}$ and $\frac{c}{d}$ is the best estimate for a certain Farey series $F_n$ then the farey median $\frac{a+b}{c+d}$ is the new estimate in the Farey series $F_{c+d}$ where there are no more fractions with denominator smaller than $c+d$ between them. Now consider $F_{120}$ and start from $\frac{0}{1}$ and $\frac{1}{1}$ and the solution is obvious.

We can apply the following method to find convergents of $\sqrt{d}$ :

Define $\sqrt{d} = [a_1,a_2,a_3,a_4...]$ .

Let $P_0 = 0$ , $P_1 = 1$ , and $P_k = a_{k-1}P_{k-1} + P_{k-2}$ .

Let $Q_0 = 1$ , $Q_1 = 0$ , and $Q_k = a_{k-1}Q_{k-1} + Q_{k-2}$ .

Then, given k>1, $\frac{P_k}{Q_k}$ will be an approximation for $\sqrt{d}$ .

Specifically, we want to find the convergents of $\sqrt{2}$ , so let $[a_1,a_2,a_3,a_4...] = [1,2,2,2...]$ .

Since we want a denominator less than $120$ , simply calculate the first few values of $Q_k$ (note that $P_i$ is relatively prime to $Q_i$ for all $i$ ):

$Q_2 = 1 \times 0 + 1 = 1$ , $Q_3 = 2 \times 1 + 0 = 2$ , $Q_4 = 2 \times 2 + 1 = 5$ , $Q_4 = 2 \times 5 + 2 = 12$ , $Q_5 = 2 \times 12 + 5 = 29$ , $Q_6 = 2 \times 29 + 12 = 70$ .

Then, $Q_7 > 120$ , so $\frac{P_6}{Q_6}$ is the best approximation to $\sqrt{2}$ with denominator less than $120$ . Then,

$P_2 = 1 \times 1 + 0 = 1$ , $P_3 = 2 \times 1 + 1 = 3$ , $P_4 = 2 \times 3 + 1 = 7$ , $P_4 = 2 \times 7 + 3 = 17$ , $P_5 = 2 \times 17 + 7 = 41$ , $P_6 = 2 \times 41 + 17 = \boxed{99}$ , which is the solution.

Code:

public class problem {
    public static void main(String[] args) {
        double p = Math.pow(2, 0.5);
        double min = 1;
        for (int i = 1; i<=120;i++) {
            double a =  Math.floor(p * i);
            double b =  Math.ceil(p * i);
            if ((p - (a/i)) < min) {
                min = p - (a/i);
                System.out.println("Found new min " + a + "/" + i + " min: " + min);
            }
            if (((b/i) - p) < min) {
                min = (b/i) - p;
                System.out.println("Found new min " + b + "/" + i + " min: " + min);
            }
        }
    }
}