# Closest rational approximation of $\sqrt x$ with denominator having prime powers $\lt n$

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.

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.
• And a smaller denominator term will never produce a better result (e.g. $2^2$ instead of $2^3$)? – hatch22 Feb 5 '15 at 16:18
• If it does, you write $p/2^2$ as $2p/2^3$. – Robert Israel Feb 5 '15 at 18:04