Rationalizing Root 2

The continued fraction expansion of square root of two is given by

1 + 1/(2 + 1/(2 + 1/(2 + 1/..........

If you truncate these, each successive truncation is the best possible rational approximation for sqrt(2) with a denominator less than or equal to this denominator. (This is a general property of continued fractions.) Doing this gives a series of approximations called the Pell numbers, which are (from http://oeis.org/A000129) the following:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, 8119/5741, 19601/13860, 47321/33461, 114243/80782, ...

Looking at the list, the biggest denominator less than 1000 is 985. The approximation is really, really close:

1393/985 = 1.414213198...... sqrt(2) = 1.414213562..... They are identical until the 7th decimal place.

This is also doable by solving Pell's equation:

a^2 - 2 b^2 = 1 for integer a and b; higher and higher values of a and b give increasingly accurate approximations.

Recall that equation $1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\ldots}}} =\sqrt{2}$ .

Hence, $\frac{1}{2+\frac{1}{2+\frac{1}{2+\ldots}}}$ is the fractional part of $\sqrt{2}$ . Therefore, we should try to stack in as many $\frac{1}{2+\ldots}$ in as possible to make the fraction close to $\sqrt{2}-1$ .

With this in mind, we calculate the value of $\frac{1}{2+\frac{1}{2}}$ first, then substitute the value into $\frac{1}{2+x}$ . Then, we keep substitute the new value we obtained from the previous substitution in place of $x$ in the equation until we obtain a denominator that is larger than 1000.

The last fraction result with denominator less than 1000 is $\frac{408}{985}$ . hence, $\frac{408}{985}+1$ is the closest to $\sqrt{2}$ with denominator less than 1000

The closest rational approximations to an irrational number are given by the truncations of its continued fraction.

$\sqrt{2} = 1 + \frac{1}{2+\frac{1}{2+\frac{1}{2+...}}}$

Truncating this fraction at successive points, one finds the following series of convergents:

$1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, ... \frac{1393}{985}, \frac{3363}{2178}$ The last fraction on this list with denominator under 1000 is 985, the answer.

We want $\frac{k}{n}$ to be as close to the square root of 2 as possible. We know that the continued fraction: $1+\frac{1}{2+\frac{1}{2+\frac{1}{2+...}}}$ is equal to the square root of 2, and by adding levels, we get that some approximations are: 1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/69, 577/408, 1393/985, and 3363/2378. So therefore, the closest approximation to the square root of 2 has a denominator less than 1000 has a denominator of 985.

The continued fraction representation of $\sqrt{2}$ is,

$\sqrt{2}$ = $1 + \frac {1}{2 + {\frac {1}{2 + \frac {1}{\frac {1}{2 + {...}}}}}}$ ,

So in order to find the approximation of $\sqrt{2}$ , we compute the successive convergents until the denominator is about to exceed 1000.

In this case, we find the largest n to be 985.

The best approximations to the square root of 2 are the convergents of its continued fraction representation (you can also see it as searching for the square root of 2 in the Stern-Brocot tree). By doing the process successively, you get 1 / 1, 3 / 2, 7 / 5, 17 / 12, 41 / 29, 99 / 70, 239 / 169, 577 / 408, 1,393 / 985. Thus the answer is 985.

Note that $\sqrt{2}=1+\sqrt{2}-1=1+\frac{1}{\sqrt{2}+1}$ . Thus, we may substitute the value of the $\sqrt{2}$ back into the expression and get the continued fraction $\sqrt{2}=1+\frac{1}{2+\frac{1}{2+\frac{1}{2+\dots}}}$ .

We can get successively better approximations of $\sqrt{2}$ by evaluating more terms of the continued fraction. For example, the simplest approximation would be $\sqrt{2}=1+\frac{1}{2}=\frac{3}{2}$ . Next, we get $\sqrt{2}=1+\frac{1}{2+1}=\frac{4}{3}$ , $\sqrt{2}=1+\frac{1}{2+\frac{1}{2}}=\frac{7}{5}$ , $\sqrt{2}=1+\frac{1}{2+\frac{1}{2+1}}=\frac{10}{7}$ , and so on. Therefore, the list of successively better approximations is $\frac{17}{12}$ , $\frac{24}{17}$ , $\frac{41}{29}$ , $\frac{58}{41}$ , $\frac{99}{70}$ , $\frac{140}{99}$ , $\frac{239}{169}$ , $\frac{338}{239}$ , $\frac{577}{408}$ , $\frac{816}{577}$ , $\frac{1393}{985}$ , $\frac{1970}{1393}$ , $\frac{3363}{2378}$ , and so on. The optimal choice under the constraints of the problem is $\frac{1393}{985}$ , so $n=985$ .

First, we rewrite $\sqrt{2}-\frac{k}{n}$ , multiplying by the conjugate and clearing the denominators: $\left|\sqrt{2}-\frac{k}{n} \right|=\frac{|2n^2-k^2|}{n^2(\sqrt{2}+\frac{k}{n})}.$

Note that for $\frac{k}{n}$ close to $\sqrt{2}$ , the denominator $n^2(\sqrt{2}+\frac{k}{n})$ is close to $2\sqrt{2}n^2$ . We will look for a number $n$ close to, but less than $1000$ , such that $2n^2-k^2 =\pm 1$ for some $k$ .

Note that $(1+\sqrt{2})(1-\sqrt{2}) = -1.$ So for every positive integer $m$ , if $(1+\sqrt{2})^m=k+n\sqrt{2},$ then $(1-\sqrt{2})^m=k-n\sqrt{2},$ and $k^2-2n^2=(k+n\sqrt{2})(k-n\sqrt{2})=(-1)^m.$

One can easily calculate $(1+\sqrt{2})^2=3+2\sqrt{2},$ $(1+\sqrt{2})^4=17+12\sqrt{2},$ $(1+\sqrt{2})^8=577+408\sqrt{2};$ $(1+\sqrt{2})^9=1393+985\sqrt{2}$ . This implies that for $n=985$ and $k=1393$ the distance between $\sqrt{2}$ and $\frac{k}{n}$ is approximately $\frac{1}{985^2(2\sqrt{2})}$ . Clearly, for another number $n<1000$ to give a better approximation, the numerator must be $1$ .

Lemma. Suppose $k$ and $n$ are positive integers such that $k^2-2n^2=\pm 1.$ Then $k+n\sqrt{2}=(1+\sqrt{2})^m$ for some non-negative integer $m$ .

Proof. This classical fact follows from the theory of Pell's equation, or the classification of units in real quadratic field ${\mathbb Q}[\sqrt{2}]$ . Here is an elementary argument. Suppose $(k,n)$ is a pair satisfying $k^2-2n^2=\pm 1,$ such that $k+n\sqrt{2}$ is not a power of $1+\sqrt{2}$ and $n$ is smallest possible. Note that the pair $(k_1,n_1)=(2n-k,k-n)$ satisfies the same equation (it was obtained by multiplying $k+n\sqrt{2}$ by $\sqrt{2}-1=\frac{1}{1+\sqrt{2}}$ ). Clearly, $n>1$ , from which one can see that $n<k<2n$ , so the new pair consists of positive numbers and has smaller $n$ . By assumption, we must have $k_1+n_1\sqrt{2} = (1+\sqrt{2})^m,$ from which $k+n\sqrt{2}=(1+\sqrt{2})^{m+1}$ , a contradiction.

To finish the problem, note that $(1+\sqrt{2})^{10}$ has $n> 1000.$ Therefore, the answer is $985$ .

The continued fraction of $\sqrt{2}$ is $[1; 2, 2, 2, \ldots]$ , and the convergents $p_n/q_n$ of the continued fraction are the best rational approximations to $\sqrt{2}$ . We compute these using $\frac{p_0}{q_0} = \frac{1}{0}, \frac{p_1}{q_1} = \frac{1}{1}$ , and the recurrence $p_{n+1} = 2p_n + p_{n-1}, q_{n+1} = 2q_n + q_{n-1}$ . This yields the sequence of convergents

$\frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \cdots$

The last of these, with denominator 985, will be the best approximation with denominator up to 1000.

The continued fraction representation of the square root of two is $1+\frac1{2+\frac1{2+\frac1{2+\cdots}}}$ . The successive approximations of this infinite fractions provide the "best" approximations of the square root of two, meaning that if $\frac{k}{n}$ is the approximation, $\left|\sqrt{2}-\frac{k}{n}\right|$ is the smallest possible for all fractions with denominator less than or equal to $n$ . We calculate the approximations until we reach $\frac{1393}{985}$ as an approximation, with approximations of higher denominator all having denominator greater than 1000 (the next is $\frac{3363}{2378}$ ). The answer is therefore 985.

I knew that continued fraction for x generates all of the best rational approximations for x. Continued fraction for \sqrt{2} is 1+\frac {1}{2+\frac {1}{2+\frac {1}{2+\ldots}}} The first convergents are: 1/1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408,1393/985

http://www.mathpath.org/Algor/squareroot/algor.myformula.htm

Let Q be a non-square integer. The Bhaskara-Brouncker Algorithm gives successive approximations of $$\sqrt{Q}$$ as $$\frac{a i}{b i}$$, where $$a 0=b 0=1$$, and $$a i+1=a i+b iQ$$ $$b i+1=a i+b i$$

Now, setting $$x i=\frac{a i}{b i}$$, we get the formula for successive approximations to $$\sqrt{Q}:$$ $$x i+1=\frac{(x i+Q)}{(x i+1)}$$ with $$x_0=1$$.

Now, substituting the values with 2 and 1000, yield $$\frac{1393}{985}.$$ Hence, the denominator is 985.