Finding Irrational Approximation for a given Rational Number.

216 Views Asked by At

Any decimal number $z$ of $n$ digits after decimal point is given. Let, $q=\frac{a^{\frac{1}{c}}}{b}$ where $a,b,c$ are integers, $c>1$.

Problem: Find smallest possible $a,b,c$ such that $q$ has same $n$ digits of $z$ after decimal point.

Note:

1.Since we are considering smallest possible $a,b,c$, please do not consider anything similar to the below method-

Excluded Method : If $z = 0.z_1z_2z_3 \dots z_n$ where $z_i \in \{0,1,\ldots,9\}$ stands for a digit .Then $z$ is rational. Now take $z' = z +( 10^{-n-1} \times q)$ .

2.There are many possible $a$, By "smallest possible" I meant, that find $a,b,c$ so that the number of total digits of $a,b,c$ is as less as possible.

1

There are 1 best solutions below

4
On

An exhaustive search can be made to find an effective solution of:

$$ 0 \le \frac{a^{1/c}}{b} - z \lt 10^{-n} $$

which minimizes the total (decimal) digits needed for $a,b,c$. Here I assume $z \gt 0$ is given as a real number to exactly $n$ places beyond the decimal (hence rational). If we were to require that $\frac{a^{1/c}}{b}$ be irrational, then the left-hand inequality would become strict (per @TonyK's Comment).

One such approach would be to consider sequentially the possible values of $b$. Note that that $b \ge 1$ must be large enough that $zb \gt 1$, since $a^{1/c}$ will be at least $1$.

Consider then the search using a fixed value of $b$, for which we continue to search using sequential values of $c \ge 1$. The finitely many values $a$ which satisfy the inequality (if any) are then easily found:

$$ (zb)^c \le a \lt ((z + 10^{-n})b)^c $$

As soon as one such combination $a,b,c$ is found, it gives an upper bound on the minimum number of digits allowed for $a,b,c$ combined. This in turn makes the search eventually terminate, e.g. when $b$ of itself reaches such a number of digits. [See the Addendum below (at end) for a sharpening of this criterion.]

Example

Let's take $z=3.14159265$, the value of $\pi$ truncated to eight decimal places, and $n=8$. The results for one digit values of $b$ (done with Google Sheets) illustrate the ease with which minimum values for $c$ and $a$ can be located.

Since $zb \gt 1$, once $c$ is large enough to admit an integer $a$ between $(zb)^c$ and $(zb + 10^{-n})^c$, increasing $c$ further would not allow $a$ to decrease. Thus, for fixed $b$ the choice of smallest $c,a$ does not involve any trade-off with counting the total digits required.

$$ \begin{array}{r|rrr} \text{digits} & b & c & a \\ \hline 11& 1 &15 & 28658146 \\ 11& 2 &9 & 15262259 \\ 10& 3 & 8 & 62254252 \\ 10& 4 & 7 & 49484484 \\ 11& 5 & 7 & 235960407 \\ 10& 6 & 6 & 44854574 \\ 11& 7 & 6 & 113106477 \\ 10& 8 & 5 & 10027653 \\ 11& 9 & 6 & 510921631 \end{array} $$

Taking for example $b=4$, $c=7$, and $a = 49484484$, we get:

$$ \frac{a^{1/c}}{b} = 3.14159265138\ldots $$

and this has used a combined ten digits among $a,b,c$. Since the target $z$ we are trying to "fit" has nine digits (including the one to the left of the decimal point), it is natural that some roughly equal sum of digits will be needed in a "generic" case.

Addendum

A brief allusion was made to terminating the search based on $b$ reaching the number of digits achieved by the best record "so far". Indeed we can sharpen this criterion significantly.

Let $b$ have $m$ digits. Since $z \gt 1$, also $zb$ has at least $m$ digits. Now $a \ge (zb)^c$, so $a$ will have at least $c(m-1)+1$ digits. As $c$ itself must have at least one digit, the total combined digits of $a,b,c$ is at least $ c(m-1) + m + 2 $.

If we have achieved a current record of say $K$ digits in an approximation, then to beat that record requires:

$$ c(m-1) + m + 2 \le K-1 $$

Thus $c \le \left\lfloor \frac{K-m-2}{m-1} \right\rfloor $, so that when $c \gt 1$ (either because the OP excludes $c=1$ or because this case would be better handled by continued fractions):

$$ 2(m-1) \le K-m-3 \\ 3m \le K-1 \\ m \le \left\lfloor \frac{K-1}{3} \right\rfloor $$

Thus in the example above, where a current record $K=10$ is quickly achieved, the improved termination criterion says we can stop searching after all three digit possibilities for $b$ are checked.