I saw an interesting problem on a reddit math forum today. The question was to find a number (x) as close as possible to r=3.6, but the requirement is that both x and 1/x be representable in a finite number of decimal places.
The problem of course is that 3.6 = 18/5. And the problem with 18/5 has an inverse 5/18, which will not have a finite representation in decimal form.
In order for a number and its inverse to both be representable in a finite number of decimal places (using base 10) we must have it be of the form 2^p*5^q, where p and q are integer, but may be either positive or negative. If that is not clear to you intuitively, suppose we have a form
2^p*5^-q
where p and q are both positive. All you need do is multiply that number by 10^q. All this does is shift the decimal point since you are just myltiplying by powers of 10. But now the result is
2^(p+q)
and that is clearly an integer, so the original number could be represented using a finite number of digits as a decimal. The same general idea would apply if p was negative, or if both of them were negative exponents.
Now, to return to the problem at hand... We can obviously adjust the number r to be 20/5 = 4, or 16/5 = 3.2. In both cases, since the fraction is now of the desired form, we are happy. But neither of them is really close to 3.6. My goal will be to find a better approximation, but hopefully, I can avoid a horrendous amount of trial and error. It would seem the trick might be to take logs, to get us closer to a solution. That is, suppose I take logs, to the base 2?
I used log2 here because that makes the problem a little simpler, since log2(2^p)=p. Therefore we want to find a pair of integers (p,q) such that
log2(3.6) + delta = p + log2(5)*q
where delta is as close to zero as possible. Thus delta is the error in our approximation to 3.6. And since we are working in logs, delta can be viewed as a proportional error term. Again, p and q may be any integers, either positive or negative. The two cases we have seen already have (p,q) = (2,0), and (4,-1).
Do you see the general idea? The line we have is of the form
log2(3.6) = p + log2(5)*q
it represents a line in the (p,q) plane, and we want to find a point on the integer lattice (p,q) where the line passes as closely as possible.
[Xl,Yl] = meshgrid([-10:10]);
fimplicit(@(p,q) -log2(3.6) + p + log2(5)*q,[-10,10,-10,10],'g-')
Now, some might think in terms of orthogonal distance to the line, but really, we want the vertical distance to be minimized. Again, minimize abs(delta) in the equation:
log2(3.6) + delta = p + log2(5)*q
where p and q are integer.
Can we do that using MATLAB? The skill about about mathematics often lies in formulating a word problem, and then turning the word problem into a problem of mathematics that we know how to solve. We are almost there now. I next want to formulate this into a problem that intlinprog can solve. The problem at first is intlinprog cannot handle absolute value constraints. And the trick there is to employ slack variables, a terribly useful tool to emply on this class of problem.
Rewrite deta as:
delta = Dpos - Dneg
where Dpos and Dneg are real variables, but both are constrained to be positive.
p = optimvar('p',lower = -50,upper = 50,type = 'integer');
q = optimvar('q',lower = -50,upper = 50,type = 'integer');
Dpos = optimvar('Dpos',lower = 0);
Dneg = optimvar('Dneg',lower = 0);
Our goal for the ILP solver will be to minimize Dpos + Dneg now. But since they must both be positive, it solves the min absolute value objective. One of them will always be zero.
prob.Constraints = log2(r) + Dpos - Dneg == p + log2(5)*q;
prob.Objective = Dpos + Dneg;
The solve is now a simple one. I'll tell it to use intlinprog, even though it would probably figure that out by itself. (Note: if I do not tell solve which solver to use, it does use intlinprog. But it also finds the correct solution when I told it to use GA offline.)
solve(prob,solver = 'intlinprog')
Solving problem using intlinprog.
Running HiGHS 1.7.1: Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [1e+00, 2e+00]
Cost [1e+00, 1e+00]
Bound [5e+01, 5e+01]
RHS [2e+00, 2e+00]
Presolving model
1 rows, 4 cols, 4 nonzeros 0s
1 rows, 4 cols, 4 nonzeros 0s
Solving MIP model with:
1 rows
4 cols (0 binary, 2 integer, 0 implied int., 2 continuous)
4 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 0 inf inf 0 0 0 0 0.0s
R 0 0 0 0.00% 0 0.765578819 100.00% 0 0 0 1 0.0s
H 0 0 0 0.00% 0 0.5905649912 100.00% 11 5 0 6 0.0s
H 0 0 0 0.00% 0 0.2686368963 100.00% 12 5 1 6 0.0s
H 0 0 0 0.00% 0 0.0875069139 100.00% 13 5 1 6 0.0s
H 0 0 0 0.00% 0 0.0532911986 100.00% 14 5 1 6 0.0s
H 0 0 0 0.00% 0 0.0190754832 100.00% 15 5 6 6 0.0s
H 0 0 0 0.00% 0 0.0151402321 100.00% 16 5 11 6 0.0s
H 0 0 0 0.00% 0 0.00115357525 100.00% 17 5 22 6 0.0s
Solving report
Status Optimal
Primal bound 0.00115357524726
Dual bound 0.00115357524726
Gap 0% (tolerance: 0.01%)
Solution status feasible
0.00115357524726 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.01 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 98 (total)
1 (strong br.)
6 (separation)
88 (heuristics)
Optimal solution found.
Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 1e-06. The intcon variables are
integer within tolerance, options.ConstraintTolerance = 1e-06.
ans =
Dneg: 0
Dpos: 0.0012
p: 39
q: -16
The solution it finds within the bounds of +/- 50 for both p and q seems pretty good. Note that Dpos and Dneg are pretty close to zero.
and while 3.6028979... seems like nothing special, in fact, it is of the form we want.
R = sym(2)^39*sym(5)^-16
R =

vpa(1/R,100)
ans = 0.277555756156289135105907917022705078125
both of those numbers are exact. If I wanted to find a better approximation to 3.6, all I need do is extend the bounds on p and q. And we can use the same solution approch for any floating point number.