1
$\begingroup$

I am representing denominators in rational numbers with powers of their prime factors for easy multiplication and division in lowest terms (by adding and subtracting the prime powers). I would like to know how to find the best rational approximation of $\sqrt x$ (with $x$ square-free) with a denominator with prime powers less than $n$.
$$ \sqrt x \approx \frac p q $$ If $n = 10$, the denominator $q$'s prime powers are limited to $2^a\times3^b\times5\times7$ where $a, b \in \mathbb Z \geq 0$ and $a \leq 3, b \leq 2$. Is there a known method to find the best rational approximation with this limitation? Continued fraction convergents do not admit a limit on the prime powers of the denominator, at least not how they are usually formulated.

$\endgroup$
1
$\begingroup$

Allowing fractions not in lowest terms, you can assume the denominator is $q = 2^3 \times 3^2 \times 5 \times 7$. Then you just want $p$ to be the closest integer to $q \sqrt{x}$.

EDIT: Note that this is assuming "best" means least $\left| \sqrt{x} - p/q \right|$. There are other notions of "best approximation", to which this would not apply.

$\endgroup$
  • $\begingroup$ And a smaller denominator term will never produce a better result (e.g. $2^2$ instead of $2^3$)? $\endgroup$ – hatch22 Feb 5 '15 at 16:18
  • $\begingroup$ If it does, you write $p/2^2$ as $2p/2^3$. $\endgroup$ – Robert Israel Feb 5 '15 at 18:04
  • $\begingroup$ In response to your edit, that is in fact what I meant by "best" and seems to be a common interpretation, which is why I said "closest" in the title (which I know is also somewhat ambiguous). $\endgroup$ – hatch22 Feb 6 '15 at 3:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.