# Tag Info

## New answers tagged continued-fractions

0

Suppose you are able to find a solution to $x^2-6y^2=1$ like $u_1=5$ and $v_1=2$ as indicated in the answer given by user17762. Then ALL other positive integer solutions $(u_n,v_n)$ can be found by $$u_n+\sqrt{6}v_n=(u_1+\sqrt{6}v_1)^n.$$ Thus another solution will be $$u_2+\sqrt{6}v_2=(u_1+\sqrt{6}v_1)^2=(5+2\sqrt{6})^2=49+20\sqrt{6}.$$ In general, you ...

1

The easiest way is to guess one positive solution, namely in this case, $(x,y) = (5,2)$. This happens to be the smallest positive solution as well. Once this is done, use Brahmagupta's identity to construct more solutions.

1

Well, according to your equations, you have to take the floor of $\frac{n+b}{d}$. In your example, it's $\left\lfloor\frac{8+8}{5} \right\rfloor = 3$. Your $p$ is then $(3 \cdot 2) - 3 = 3$, and your $q$ is $(3 \cdot 5) - 8 = 7$.

0

As you observed, the $n$-th convergent of the continued fraction $[a_0; a_1,a_2,\dotsc]$ is the rational number $$c_n = [a_0; a_1,\dotsc,a_n] = a_0 + \cfrac{1}{a_1 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}$$ and the integers $p_n,q_n$ are simply numerator and denominator of $c_n$, respectively. In particular, $c_0 = a_0 \in \Bbb{Z}$ has denominator ...

0

The problem turned out to be a very simple reading error on my part. In fact Khichin's $p'_r/q'_r$ is not the $r$-th convergent of the original continued fraction $$[a_0; a_1, ... a_n]$$, but of the continued fraction $$[a_1; a_2, ..., a_n]$$ in which case his claim is obvious.

0

in the middle of page 3, not numbered, he says $$[a_0; a_1, \ldots, a_n] = [a_0; r_1] = a_0 + \frac{1}{r_1}.$$ Here, $$r_1 = [a_1; a_2, \ldots, a_n]$$ which is consistent with your (*), this being formula (6) on page 4. Meanwhile, I have gotten good use out of these for years, I recommend you get accustomed to this slang for writing the ...

3

As per TonyK's answer, it is only necessary to find the smallest denominator for which a fraction in $[L,U)$ exists. To avoid what he calls "messy" oscillations, we can proceed as follows: Start with $(a,b,c,d)=(0,1,1,1)$. *[Remark: We have $\frac ab<L<U\le \frac cd$, and $ad-bc=-1$, and any fraction between $\frac ab$ and $\frac cd$ has denominator ...

3

It is enough to find the smallest possible $b$, and then the smallest possible $a$ given $b$. This is not completely obvious, so I will try to prove it: Suppose we have positive integers $a,b$ such that (i) $b$ is the smallest denominator of all fractions in $[L,U)$; and (ii) $a/b$ is the smallest multiple of $1/b$ in $[L,U)$. This means ...

1

Why is your algorithm exponential? Here's an option: Don't think about the numbers as fractions, but as pairs. Your goal is to find the pair $(a,b)$ such that $L\leq a/b\leq U$ such that $a\times b$ is minimal. In this case, we do NOT reduce fractions. For a fixed $b$, we can easily find the smallest possible $a$ that satisfies the conditions by ...

Top 50 recent answers are included