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.

Solution 1:

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.$$

Solution 2:

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$.