# A friend chooses two 5 digit positive integers with no common factors and divides one by the other, telling you the result to 12 significant digits. How can you find out what the two numbers were?

Nov 10, 2016

See below.

#### Explanation:

This problem has a "brute force" solution, using an optimization procedure.

Supose we know $f$ a $12$ digit precission associated to a fraction $\frac{n}{m}$ with $n , m$ two $5$ digit integer numbers. So

$n = {\sum}_{k = 0}^{4} {a}_{k} {10}^{k}$ and
$m = {\sum}_{k = 0}^{4} {b}_{k} {10}^{k}$

Defining now

$e = n - f \cdot m$ we can formulate a Linear Programming model with integer restrictions, that could conveniently minimize the objetive function ${\lambda}_{s} - {\lambda}_{i}$ such that

${S}_{\lambda} = \left\{{\mu}_{i} \le {\lambda}_{i} \le e \le {\lambda}_{s} \le {\mu}_{s}\right\}$

with the integer restrictions

S_a = {0 le a_k le 9 for $k = 0 , 1 , 2 , 3$ and 1 le a_4 le 9} and ${a}_{k} \in \mathbb{N}$
S_b = {0 le b_k le 9 for $k = 0 , 1 , 2 , 3$ and 1 le b_4 le 9} and ${b}_{k} \in \mathbb{N}$

The final model is

$\min {\lambda}_{s} - {\lambda}_{i}$

subjected to

$S = {S}_{\lambda} \cap {S}_{a} \cap {S}_{b}$

Here ${\mu}_{i}$ and ${\mu}_{s}$ are margins with the purpose of precision enhancement. Have in mind that Integer programming is not convex programming. Typical values for ${\mu}_{i}$ and ${\mu}_{s}$ are $- {10}^{- 4}$ and ${10}^{- 4}$ respectively.

1) Given $f = 0.764003200360$ the procedure obtained
$n = 13367$
$m = 17496$

2) Given $f = 5.83081793383$ the procedure obtained
$n = 79200$
$m = 13583$

2) Given $f = 3.14159265359$ the procedure obtained
$n = 92988$
$m = 29599$

Nov 10, 2016

Use continued fractions...

#### Explanation:

If the quotient was known exactly then we could recover the original numerator and denominator by calculating the continued fraction, which would terminate, then simplifying.

As it is, we know the quotient to $12$ significant digits, which should be enough. We just have to recognise when we have encountered the rounding error introduced by the $12$ significant figure approximation...

Given the quotient, calculate the continued fraction as follows:

• Write down the integer part and subtract it.

• If the result is zero (or near enough) then stop.

• Otherwise take the reciprocal and repeat.

The sequence of numbers written down form the coefficients of the continued fraction.

For example, suppose your friend told you that the quotient was: $0.357132525241$ to $12$ significant digits.

Following the steps above:

• Write down the integer part $\textcolor{b l u e}{0}$ and subtract it to give: $0.357132525241$

• Take the reciprocal to give: $2.80008100445$

• Write down the integer part $\textcolor{b l u e}{2}$ and subtract it to give: $0.80008100445$

• Take the reciprocal to give: $1.24987344336$

• Write down the integer part $\textcolor{b l u e}{1}$ and subtract it to give: $0.24987344336$

• Take the reciprocal to give: $4.00202593182$

• Write down the integer part $\textcolor{b l u e}{4}$ and subtract it to give: $0.00202593182$

• Take the reciprocal to give: $493.600026480$ (looks like we're getting warm)

• Write down the integer part $\textcolor{b l u e}{493}$ and subtract it to give: $0.600026480$

• Take the reciprocal to give: $1.66659311436$

• Write down the integer part $\textcolor{b l u e}{1}$ and subtract it to give: $0.66659311436$

• Take the reciprocal to give: $1.50016551095$

• Write down the integer part $\textcolor{b l u e}{1}$ and subtract it to give: $0.50016551095$

• Take the reciprocal to give: $1.99933817528$

• That's pretty close to our final integer $\textcolor{b l u e}{2}$

Taking the integers we have written down, we get the continued fraction:

""[color(blue)(0); color(blue)(2), color(blue)(1), color(blue)(4), color(blue)(493), color(blue)(1), color(blue)(1), color(blue)(2)] = color(blue)(0) + 1/(color(blue)(2) + 1/(color(blue)(1) + 1/(color(blue)(4) + 1/(color(blue)(493) + 1/(color(blue)(1) + 1/(color(blue)(1) + 1/color(blue)(2)))))))

color(white)(""[0; 2, 1, 4, 493, 1, 1, 2]) = 0+1/(2+1/(1+1/(4+1/(493+1 /(1+2/3)))))

color(white)(""[0; 2, 1, 4, 493, 1, 1, 2]) = 0+1/(2+1/(1+1/(4+1/(493+3/5))))

color(white)(""[0; 2, 1, 4, 493, 1, 1, 2]) = 0+1/(2+1/(1+1/(4+5/2468)))

color(white)(""[0; 2, 1, 4, 493, 1, 1, 2]) = 0+1/(2+1/(1+2468/9877))

color(white)(""[0; 2, 1, 4, 493, 1, 1, 2]) = 0+1/(2+9877/12345)

color(white)(""[0; 2, 1, 4, 493, 1, 1, 2]) = 0+12345/34567

color(white)(""[0; 2, 1, 4, 493, 1, 1, 2]) = 12345/34567

So the original two $5$ digit numbers were $12345$ and $34567$.