Question

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?

Answer 1

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 `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)={mu_ile lambda_i le e le lambda_sle mu_s}`

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 NN`
`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 NN`

The final model is

`min lambda_s-lambda_i`

subjected to

`S = S_(lambda) nn S_a nn 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.

Follow some samples:

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`

Answer 2

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 `color(blue)(0)` and subtract it to give: `0.357132525241`

• Take the reciprocal to give: `2.80008100445`

• Write down the integer part `color(blue)(2)` and subtract it to give: `0.80008100445`

• Take the reciprocal to give: `1.24987344336`

• Write down the integer part `color(blue)(1)` and subtract it to give: `0.24987344336`

• Take the reciprocal to give: `4.00202593182`

• Write down the integer part `color(blue)(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 `color(blue)(493)` and subtract it to give: `0.600026480`

• Take the reciprocal to give: `1.66659311436`

• Write down the integer part `color(blue)(1)` and subtract it to give: `0.66659311436`

• Take the reciprocal to give: `1.50016551095`

• Write down the integer part `color(blue)(1)` and subtract it to give: `0.50016551095`

• Take the reciprocal to give: `1.99933817528`

• That's pretty close to our final integer `color(blue)(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`.