0
$\begingroup$

I'd like to know how to find a sequence of digits (say up to 32 digits with each digit chosen from $\{0,\dots,9\}$) in the decimal expansion of some $p/q$ with $p < q < 10000$.

I've tried brute force methods, checking each $1/9999$, $2/9999$, etc. but it takes way too long. Any ideas?

$\endgroup$
  • $\begingroup$ long division heh $\endgroup$ – Saketh Malyala Apr 2 '17 at 20:27
  • $\begingroup$ Could you be a bit more specific please? $\endgroup$ – Kanesc2 Apr 2 '17 at 20:30
  • $\begingroup$ The decimal expansion is periodic, with the period depending on q. You'll need to choose specific values q to guarantee that the period is of length at least 32 at all, if your sequence is not periodic. $\endgroup$ – TMM Apr 3 '17 at 0:22
0
$\begingroup$

You won't always be able to find a fraction $\frac pq$ with $p < q < 10000$ containing your sequence, but if you can do it, here's how.

First, if any such fraction contains your sequence at all, then some such fraction must begin with your sequence. To see this, notice that if $\frac pq$ contains your sequence starting from the $k^{\text{th}}$ digit after the decimal, then $\frac{10p \bmod q}{q}$ (the fractional part of $\frac{10p}{q}$) contains it starting from the $(k-1)^{\text{th}}$ digit.

So if you're looking for a sequence $s_1s_2\dots s_n$, we might as well look for a fraction beginning $0.s_1s_2\dots s_n$, so let's find good approximations of the rational number $r = 0.s_1s_2\dots s_n5$. (I add the $5$ at the end to make $r$ the midpoint of the interval of all real numbers beginning with this sequence.)

We can find good approximations of $r$ from its continued fraction expansion. This is an expression of the form $$r = a_0 + \frac1{a_1 + \frac1{a_2 + \frac1{a_3 + \frac1{\ddots}}}}$$ which we can find iteratively: find $a_0$ by taking $\lfloor r \rfloor$, and then finding the continued fraction expansion of $\frac1{r - a_0}$ to get $a_1, a_2, \dots$.

Because $r$ is rational, eventually this process stops, giving us exactly $r$. But truncating this expansion, but using less of the sequence $a_0, a_1, a_2, \dots$, gives us approximations $\frac{p_0}{q_0}, \frac{p_1}{q_1}, \frac{p_2}{q_2}, \dots$ where $$\frac{p_0}{q_0} = a_0, \quad \frac{p_1}{q_1} = a_0 + \frac1{a_1}, \quad \frac{p_2}{q_2} = a_0 + \frac1{a_1 + \frac1{a_2}}, \quad \dots$$ See Wikipedia. These also satisfy the recurrence $\frac{p_{k+2}}{q_{k+2}} = \frac{p_k + a_{k+2} p_{k+1}}{q_k + a_{k+2} p_{k+1}}$.

These are best approximations in the sense that $\left|r - \frac{p_k}{q_k}\right| < \left|r - \frac{p'}{q'}\right|$ for any $p', q'$ with $q' < q_k$. So we can find better and better approximations for $r$, and if eventually one of them starts with $0.s_1s_2\dots s_n$, we're done.

It's possible that we've gotten to approximations $\frac{p_k}{q_k}$ where $q_k \ge 10000$ and we still don't have a good enough approximation of $r$. If that's the case, we give up: by the best approximation inequality,no $\frac pq$ with $q < 10000$ can be good enough.

Finally, we can end up in the rare but annoying edge case where $\frac{p_k}{q_k}$ is the last approximation with $q_k < 10000$, and is not good enough, but $\frac{p_{k+1}}{q_{k+1}}$ is good enough (and has $q_{k+1} \ge 10000$). If that's the case, we have two last resorts:

  • The semi-convergents: see this blog post. These are computed by taking $\frac{p_{k-1} + n p_k}{q_{k-1} + n q_k}$ for $1 \le n < a_{k+1}$, and also satisfy the best approximation inequality.
  • If that's still inconclusive, then let $\frac{p}{q}$ be the best approximation we've found so far, and try denominators of $q+1, q+2, \dots, 9999$ by brute force. To try a denominator of $m$, take the fractions $\frac{\lfloor{rm}\rfloor}{m}$ and $\frac{\lceil{rm}\rceil}{m}$ and see if either of them work.
$\endgroup$

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.