Find the minimum of $q$. 
Given $\displaystyle p,q\in\mathbb N, \frac p q=0.123456789...$(i.e. the first 9 digits after decimal point are $123456789$). Find the minimum of $q$.

I guessed the answer to be $111111111$ as $\displaystyle\frac {123456789} {999999999}=0.\dot{1}2345678\dot{9}$, but I'm not sure.
Thank you.
 A: The smallest $q$ is $q=10989019$ corresponding to $$\frac pq=\frac{1356669}{10989019}=0.12345678900000081899940294943524986\ldots$$
To see this, note that
$$ \frac ab=\frac{1356659}{10988938}=0.1234567889999925379504370668029977\ldots$$
is too small and
$$\frac cd=\frac{10}{81}=0.12345679012345679012345679012345679\ldots$$
is too big.
For any fraction with $\frac ab<\frac pq<\frac cd$, we have
$$\frac pq-\frac ab=\frac{bp-aq}{bq}>0\qquad\frac cd-\frac pq=\frac{cq-dp}{dq}>0,$$
hence $$ bp-aq\ge 1\qquad cq-dp\ge 1$$
and finally (because $bc-ad=1$)
$$ q=(bc-ad)q=d(bp-aq)+b(cq-dp)\ge b+d=10989019.$$
A: Here is the magic algorithm which Hagen von Eitzen used to compute the answer.
This method is extremely elegant, and is derived from Farey sequences.
To shorten the computation, I will solve the analagous question of finding the smallest $q$ such that $\frac{p}{q}$ has decimal expansion $.789....$.
Let $\alpha = \frac{789}{1000}$; we are looking for rational numbers close to $\alpha$ with small denominators.  (In general, $\alpha$ can be any positive real number.)
Start with the two fractions $\frac01$ and $\frac10$.
Note that $\frac01 < \alpha < \frac10$.
Add the numerators and add the denominators to get the fraction
$\frac{0 + 1}{1 + 0} = \frac11$.  Of the three fractions we have listed so far ($\frac01, \frac11,$ and $\frac10$), take the two that are on either side of $\alpha$, i.e. $\frac01$ and $\frac11$.
We have the two fractions $\frac01$ and $\frac11$, with $\frac01 < \alpha < \frac11$.
Add the numerators and denominators to get $\frac{0 + 1}{1 + 1} = \frac12$.  Of the three fractions $\frac01$, $\frac12$, and $\frac11$, $\alpha$ is between $\frac12$ and $\frac11$, so take these two.
We have the two fractions $\frac12$ and $\frac11$.
Add the numerators and denominators to get $\frac{1 + 1}{2 + 1} = \frac23$.  Of the three fractions $\frac12$, $\frac23$, $\frac11$, $\alpha$ is between
$\frac23$ and $\frac11$, so take these two.
You can see where this is going.  Next we get the pairs of fractions $\frac34$ and $\frac11$, then $\frac34$ and $\frac45$, then $\frac79$ and $\frac45$, then $\frac{11}{14}$ and $\frac45$, then $\frac{15}{19}$ and $\frac{4}{5}$.
We stop because $\frac{15}{19}$ has decimal expansion $.789....$ (it is the first of the fractions we have listed).  This is the answer.  No matter what decimal expansion you want ($.123456789$ in your case), this method will always eventually give you the fration $\frac{p}{q}$ with minimum $q$.
