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

• There more digits after that. – A. Chu May 18 '13 at 14:07
• @julien: Just the first nine digits are known, the digits after that can be anything. – Inceptio May 18 '13 at 14:11
• @Inceptio They can't be anything, because it has to be a rational number, if I understand the question. So the decimal expansion either terminates, or is eventually periodic. – Julien May 18 '13 at 14:15
• Yeah, it has to be a rational number. But what values after those nine digits makes the value of $q$ minimum. $0's$, of course. – Inceptio May 18 '13 at 14:16
• @Inceptio No. For instance $123456789/10^9=0.123456789<123456789/999999999=0.12345678912$, yet $10^9>999999999$. – Julien May 18 '13 at 14:21

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

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

• how have you reach at this $q?$ – lab bhattacharjee May 18 '13 at 14:18
• And how's it the minimum value? – Inceptio May 18 '13 at 14:18
• To see where the magic comes from, look up Farey sequences. – Hagen von Eitzen May 18 '13 at 14:27
• @julien: I don't think so using the Farey sequence. The problem is that $\frac {10}{81}$ is so close. The denominator only increases by $81$ each time, so it will take something like $135700$ steps. But it only takes four steps of the continued fraction, so that would be doable by hand. – Ross Millikan May 18 '13 at 15:02
• @julien: it doesn't seem to work too well, either. The next approximant after $\frac {10}{81}$ is $\frac {1356659}{10988938}$ in the continued fraction approximation [0;8,9,1,135665,1]. This doesn't seem to fit the Wikipedia article on best rational approximations – Ross Millikan May 18 '13 at 15:53