11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There more digits after that. $\endgroup$ – A. Chu May 18 '13 at 14:07
  • 1
    $\begingroup$ @julien: Just the first nine digits are known, the digits after that can be anything. $\endgroup$ – Inceptio May 18 '13 at 14:11
  • 2
    $\begingroup$ @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. $\endgroup$ – Julien May 18 '13 at 14:15
  • $\begingroup$ 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. $\endgroup$ – Inceptio May 18 '13 at 14:16
  • 1
    $\begingroup$ @Inceptio No. For instance $123456789/10^9=0.123456789<123456789/999999999=0.12345678912$, yet $10^9>999999999$. $\endgroup$ – Julien May 18 '13 at 14:21
5
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ how have you reach at this $q?$ $\endgroup$ – lab bhattacharjee May 18 '13 at 14:18
  • $\begingroup$ And how's it the minimum value? $\endgroup$ – Inceptio May 18 '13 at 14:18
  • 5
    $\begingroup$ To see where the magic comes from, look up Farey sequences. $\endgroup$ – Hagen von Eitzen May 18 '13 at 14:27
  • 2
    $\begingroup$ @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. $\endgroup$ – Ross Millikan May 18 '13 at 15:02
  • 1
    $\begingroup$ @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 $\endgroup$ – Ross Millikan May 18 '13 at 15:53

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.