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?
2 Answers
See below.
Explanation:
This problem has a "brute force" solution, using an optimization procedure.
Supose we know
Defining now
with the integer restrictions
The final model is
subjected to
Here
Follow some samples:
1) Given
2) Given
2) Given
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
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:
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