P/Q is a fraction with the smallest positive integer denominator that satisfy the undernoted inequality:
386 P 35
----- < --- < ----
2019 Q 183
where P is also a positive integer.
Determine the minimum value of P+Q
The program uses a Euclidean algorithm that ordinarily is used in finding the GCD of two integers, but in this instance tries to get a rational number as close to zero difference from a "real number" goal by keeping track of how many times the original number is included and how many times a 1 is included. The goal is varied from the lower fraction to the higher one in ten steps. As soon as a number is found, the algorithm stops.
Two vector matrices keep track of the numerator and denominator, which are actually the coefficients for the goal to be reached using the goal and the integer 1 and therefore are one positive and one negative, so that has to be changed to absolute values in what we are seeking.
clc
low=386/2019, high=35/183
for goal=low:(high-low)/10:high
disp([low high])
disp(goal)
disp(' ')
a=goal;
b=1;
aSet=[1 0];
bSet=[0 1];
for i=1:15
q=floor(a/b);
r=a-q*b;
cSet=aSet-q*bSet;
a=b; b=r;
aSet=bSet; bSet=cSet;
disp([r cSet(1) cSet(2) cSet(2)/cSet(1) cSet(1)/cSet(2)])
if abs(cSet(1)/cSet(2))>low && abs(cSet(1)/cSet(2))< high ...
|| abs(cSet(2)/cSet(1))>low && abs(cSet(2)/cSet(1))< high
break
end
end
disp(' ')
end
The best fit of the 11 resulting trials finds 48/251 ~= 0.191235059760956, which fits between the given fractions which are, in approximation, 0.191183754333829 and 0.191256830601093.
The total of the numerator plus denominator is 299.
The three middle trials all show 48/251 as the best value that fits.
Output:
0.191183754333829 0.191256830601093
0.191234907720914
0.191234907720914 1 0 0 Inf
0.0438254613954319 -5 1 -0.2 -5
0.0159330621391862 21 -4 -0.19047619047619 -5.25
0.0119593371170595 -47 9 -0.191489361702128 -5.22222222222222
0.00397372502212662 68 -13 -0.191176470588235 -5.23076923076923
3.81620506796909e-05 -251 48 -0.191235059760956 -5.22916666666667
Annotated:
Acceptable bounds (exclusive): 0.191183754333829 0.191256830601093
Goal: 0.191234907720914
Amount left over trial num approximate reciprocal
and den value
0.191234907720914 1 0 0 Inf
0.0438254613954319 -5 1 -0.2 -5
0.0159330621391862 21 -4 -0.19047619047619 -5.25
0.0119593371170595 -47 9 -0.191489361702128 -5.22222222222222
0.00397372502212662 68 -13 -0.191176470588235 -5.23076923076923
3.81620506796909e-05 -251 48 -0.191235059760956 -5.22916666666667
The reciprocal is shown in the output as I wasn't sure which was to be the approximation to the goal.
|
|
Posted by Charlie
on 2022-12-02 10:10:13 |
computer solution
