Can any positive real be approximated as $2^m/3^n$ with $(m,n)$ large enough?
Conjecture.
There exist positive integers $(m,n)$ large enough, such that for any positive real number $r$ and a given error $\epsilon$ :
$$
\left| r - \frac{2^m}{3^n} \right| < \epsilon
$$
There is numerical evidence for this conjecture. I have tried $r = \sqrt{2}$ and $\epsilon = 10^{-3}$.
Below is a little Delphi Pascal program with accompanying output.
But .. can somebody prove the conjecture?
program apart;
procedure test(r : double; eps : double); var a : double; m,n : integer; begin a := 1; m := 0; n := 0; while true do begin if a < r then begin m := m + 1; a := a * 2; end else begin n := n + 1; a := a / 3; end; if abs(r-a) < eps then Break; end; Writeln(r,' = 2^',m,'/3^',n,' =',a); end;
begin test(sqrt(2),1.E-3); end.
Output:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935359E+0000
UPDATE.
The answer by lhf does look like a very concise proof. But for me - as an retired physicist by education - it's a bit beyond comprehension.
Furthermore, it leaves a few issues untouched. One might ask for example whether there are estimates for $m$ and $n$ when $r$ and $\epsilon$ are given.
Note. The question can also be formulated as: Can any positive real be approximated as $3^m/2^n$ with $(m,n)$ large enough? Which is the same as allowing negative integers with the original formulation. In this form, it shows some resemblance to the (in)famous Collatz problem.
EDIT.
As suggested by the answers, an approach with logarithms could be more effective:
program anders;
procedure proef(r : double; eps : double); var a,l2,l3,lr : double; m,n : integer; begin l2 := ln(2); l3 := ln(3); lr := ln(r); a := 0; m := 0; n := 0; while true do begin a := m*l2 - n*l3 - lr; if abs(a) < eps then Break; if a < 0 then m := m + 1 else n := n + 1; end; Writeln(r,' = 2^',m,'/3^',n,' =',exp(a)*r); end;
begin proef(sqrt(2),1.E-3); proef(sqrt(2),1.E-9); end.
Output:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935356E+0000 1.41421356237310E+0000 = 2^911485507/3^575083326 = 1.41421356125035E+0000
The first line in the output is almost identical to the result obtained previously .
The last line in the output shows that the latter approach indeed is more effective.
The error plays the same role in both approaches. Oh well, almost.
Let's take a look at the places where the 'Break's are. First program:
$$
\left| r - \frac{2^m}{3^n} \right| < \epsilon
$$
Second program:
$$
-\epsilon < m\ln(2) - n\ln(3) - \ln(r) < +\epsilon \\
\ln(1-\epsilon) < \ln\left(\frac{2^m/3^n}{r}\right) < \ln(1+\epsilon) \\
-\epsilon < \frac{2^m/3^n}{r} - 1 < +\epsilon \\
\left| r - \frac{2^m}{3^n} \right| < \epsilon.r
$$
So $\epsilon$ in the first program is an absolute error,
while $\epsilon$ in the second program is a relative error.
Continuing story at:
Can the Stern-Brocot tree be employed for better convergence of $2^m/3^n$?
Solution 1:
Let $G= \mathbb Z \log 2 + \mathbb Z \log 3$. Then $G$ is an additive subgroup of $\mathbb R$. Since $\log 2 / \log 3$ is irrational, $G$ cannot be cyclic [1] and so must be dense [2]. Therefore, $\log r$ is arbitrarily approximated by elements of $G$.
[1] If $G = \mathbb Z \theta $, then $\log 2 = a \theta$ and $\log 3 = b \theta$ and so $\log 2 / \log 3 = a/b $ is rational.
[2] See https://math.stackexchange.com/a/889775/589
Solution 2:
Yes, there are always solutions $(m, n)$ for any positive real $r$ and $\epsilon$ for $$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$ And there's a much more efficient way to find those solutions than stepping through $m$ and $n$ values one by one.
We have $$r \approx 2^m/3^n$$ Taking logarithms, $$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$ i.e., $$\log_2 r\approx m - n\log_2 3$$
[Incidentally, $$1 = \frac m{\log_2r}-\frac n{\log_3r}$$ which is a line in the $(m,n)$ plane with $m$ intercept $\log_2r$ and $n$ intercept $-\log_3r$. We want to find when that line passes close to integer $(m, n)$ lattice points].
We can find rational approximations to both those base 2 logarithms to any desired precision. However, to satisfy that equation with integer $m$ and $n$, the denominators of our approximations must be commensurate.
Let $$\log_2 r = f \approx s/t$$ and $$\log_2 3 \approx p/q$$ with the fractions being in lowest terms, i.e., $\gcd(s,t)=gcd(p,q)=1$.
Then $$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$ Thus $t|sq$. But $s$ & $t$ are coprime, hence $t|q$.
Let $q=tk$. $$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$ for some integer $d$.
So, for a given approximation $\frac pq$ to $\log_2 3$, the best rational approximations to $f$ with commensurate denominators are $\frac{d_0}q$ and $\frac{d_1}q$, where $d_0=\lfloor fq\rfloor$ and $d_1=\lceil fq\rceil$. That is, $$\frac{d_0}q \le f \le \frac{d_1}q$$ If $f$ is rational (eg, when $r=\sqrt 2$), then $d_0$ and $d_1$ may be equal.
So for a given $p$ & $q$ we just need to find integers $m$ & $n$ that solve our revised equation $$\frac dq = m - n \frac pq$$ $$d=qm-pn$$ for both $d_0$ and $d_1$. There are solutions for any integer $d$ because $p$ & $q$ are coprime. And those solutions can be found using the extended Euclidean algorithm.
But we also need to find suitable $p$ & $q$. That can be done using the convergents of the continued fraction expansion of $\log_2 3$. The standard algorithm for computing a continued fraction is closely related to the extended Euclidean algorithm, and as that Wikipedia article explains (in Theorem 3), if the $n$th convergent of a continued fraction is $\frac{h_n}{k_n}$ then $$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$ which enables us to find $m$ and $n$ without doing a separate Euclidean algorithm calculation.
The continued fraction convergent $\frac hk$ of a number $x$ gives the best rational approximations to $x$ for any denominator $\le k$. The error is $$\left|x - \frac hk\right| \le \frac 1{k^2}$$ and it can often be much better. In contrast, the error for an approximation $\frac hk$ with a "random" denominator (i.e., not a continued fraction convergent) is generally around $\frac 1{2k}$.
Unfortunately, because of the need for commensurate denominators in our approximations to the two logarithms, we don't get the full $\frac 1{k^2}$ goodness. But we do generally get better than $\frac 1{k}$.
So to find solutions with better error than a given $\epsilon$, we just need to look at the convergents to $\log_2 3$ with denominators in the neighbourhood of $\frac 1\epsilon$.
Here is some Sage / Python code that performs that task. Sage is a collection of mathematical libraries built on top of the popular Python programming language. It has arbitrary precision arithmetic, and facilities for performing symbolic algebra, but I've (mostly) avoided Sage features in this code (apart from the arbitrary precision arithmetic), to make it easier to port to other languages, if desired; I've also avoided most "Pythonisms", apart from Python's ability to return multiple values from a function.
# Numeric precision. Standard IEEE 754 binary64
# numbers (aka doubles) have 53 bits of precision.
bits = 53
# Limit the length of the continued fraction
depth = 20
def dio(q, p, x, y, d):
""" Given q, p, x, y: q*x - p*y == 1,
find the smallest m, n > 0:
q*m - p*n == d
"""
m = x * d
n = y * d
u = min(m // p, n // q)
m -= u * p
n -= u * q
assert q*m - p*n == d
return m, n
log2 = log(2).n(bits)
log3 = log(3).n(bits)
def func(m, n):
""" Calculate 2**m / 3**n """
# The naive form is too slow for large args,
# and chews up a lot of RAM because it uses
# arbitrary precision integer arithmetic.
# So we use logs instead.
#return (2**m / 3**n).n(bits)
return exp(m * log2 - n * log3).n(bits)
def cont_frac(f, depth):
""" Build lists of the convergents of
the continued fraction of f
"""
f = f.n(bits)
num = [0, 1]
den = [1, 0]
for i in range(depth):
a = floor(f)
n = num[-2] + a * num[-1]
d = den[-2] + a * den[-1]
#print(a, n, d)
num.append(n)
den.append(d)
f -= a
if f < 1e-10:
break
f = 1 / f
return num, den
num, den = cont_frac(log(3, 2), depth)
@interact
def main(r=sqrt(2), epsilon=1/1000):
print("r:", r.n(bits))
f = log(r, 2)
s = 1
digits = 2
for i in range(3, depth+2):
s = -s
p = num[i]
q = den[i]
x = num[i-1] * s
y = den[i-1] * s
assert q*x - p*y == 1
fq = f * q
d0 = floor(fq)
d1 = ceil(fq)
print(f"\n{i}: {p} / {q}, {d0} {d1}")
dseq = [d0]
if d0 < d1:
dseq = [d0, d1]
else:
dseq = [d0]
for d in dseq:
m, n = dio(q, p, x, y, d)
v = func(m, n)
eps = abs(r - v).n(bits)
if eps > 0:
digits = 1 - floor(log(eps, 10))
print(f"m: {m}, n: {n}")
print(f"v: {v:.{digits}f}, eps: {eps:.3e}")
if eps < epsilon:
return
Here's the output of that program, searching for solutions with $\epsilon=10^{-6}$:
r: 1.41421356237310
3: 2 / 1, 0 1
m: 0, n: 0
v: 1.00, eps: 4.142e-1
m: 1, n: 0
v: 2.00, eps: 5.858e-1
4: 3 / 2, 1 1
m: 2, n: 1
v: 1.333, eps: 8.088e-2
5: 8 / 5, 2 3
m: 2, n: 1
v: 1.333, eps: 8.088e-2
m: 7, n: 4
v: 1.58, eps: 1.660e-1
6: 19 / 12, 6 6
m: 10, n: 6
v: 1.4047, eps: 9.550e-3
7: 65 / 41, 20 21
m: 10, n: 6
v: 1.4047, eps: 9.550e-3
m: 56, n: 35
v: 1.440, eps: 2.603e-2
8: 84 / 53, 26 27
m: 10, n: 6
v: 1.4047, eps: 9.550e-3
m: 75, n: 47
v: 1.4209, eps: 6.645e-3
9: 485 / 306, 153 153
m: 243, n: 153
v: 1.41494, eps: 7.230e-4
10: 1054 / 665, 332 333
m: 812, n: 512
v: 1.41343, eps: 7.844e-4
m: 243, n: 153
v: 1.41494, eps: 7.230e-4
11: 24727 / 15601, 7800 7801
m: 12891, n: 8133
v: 1.414196, eps: 1.800e-5
m: 11837, n: 7468
v: 1.414257, eps: 4.373e-5
12: 50508 / 31867, 15933 15934
m: 12891, n: 8133
v: 1.414196, eps: 1.800e-5
m: 37618, n: 23734
v: 1.4142213, eps: 7.728e-6
13: 125743 / 79335, 39667 39668
m: 88126, n: 55601
v: 1.4142110, eps: 2.546e-6
m: 37618, n: 23734
v: 1.4142213, eps: 7.728e-6
14: 176251 / 111202, 55601 55601
m: 88126, n: 55601
v: 1.4142110, eps: 2.546e-6
15: 301994 / 190537, 95268 95269
m: 88126, n: 55601
v: 1.4142110, eps: 2.546e-6
m: 213869, n: 134936
v: 1.4142162, eps: 2.637e-6
16: 16785921 / 10590737, 5295368 5295369
m: 8241964, n: 5200100
v: 1.414213479, eps: 8.295e-8
And here is a live version that you can play with on the SageMath server. My code isn't stored on the server, it's encoded in the URL.
If you get weird behaviour with small $\epsilon$, try increasing the number of the bits global variable (at the top of the file). The default setting of 53 should be ok for $\epsilon > 10^{-8}$ or so. You may also need to increase the depth of the continued fraction.
FWIW, $\log_2 3$ is rather important in the mathematical music theory of equally-tempered scales. The standard 12 tone scale uses the convergent $19/12$.
Solution 3:
Heuristics of a another proof
Lemma 1.
The fractions $2^m/3^n$ are all between $r/3$ and $2r$.
Proof.
According to the program - as displayed in the question. Any fraction smaller than $r$ is multiplied by $2$,
so $r.2$ is an upper bound for these fractions. Any fraction greater than $r$ is divided by $3$, so $r/3$
is a lower bound for these fractions. There can be no other fractions, except when the iterations start.
$$
r/3 < \frac{2^m}{3^n} < 2r
$$
Lemma 2.
In the sequence $2^m/3^n \to r$ there are no two fractions the same.
Proof.
Suppose that we have $2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Three cases are distinguished:
-
$m_1 \neq m_2$ and $n_1 = n_2$. Then $2^{m_1} = 2^{m_2}$ hence $m_1 = m_2$. Contradiction.
-
$n_1 \neq n_2$ and $m_1 = m_2$. Then $1/3^{n_1} = 1/3^{n_2}$ hence $n_1 = n_2$. Contradiction.
-
$m_1 \neq m_2$ and $n_1 \neq n_2$. Then we have:
$$
\ln\left(\frac{2^{m_1}}{3^{n_1}}\right) = \ln\left(\frac{2^{m_2}}{3^{n_2}}\right) \quad \Longrightarrow \\
(m_1-m_2)\ln(2) - (n_1-n_2)\ln(3) = 0 \quad \Longrightarrow \\ \frac{m_1-m_2}{n_1-n_2} = \frac{\ln(3)}{\ln(2)}
$$
But $\,\ln(3)/\ln(2)\,$ is not a rational number. Contradiction.
So what we have is a bunch of fractions, all different, but they must fit within the interval $\,]r/3,2r[\,$. This means that the fractions become crowded. Let's make a picture of the iteration process, logarithmic version. The red line is given by $\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, small circles are fractions, mapped on a grid $\,m/n \to (m,n)\,$, massively black filled dots are the fractions in the iteration process, while increasing $m$ and $n$ with increments one at a time. The iterations domain is limited by: $\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. In our case $r = 100$. Mind the sequence at the start.
So it seems that there must be quite some fractions nearby the red line, rerpesenting the real number $r$ in question.
How can we be sure about this? Let's make picture of the crowding of the approximations $a$ in the interval $\,]r/3,2r[\,$,
logarithmic scale:
$$
a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2)
$$
The red line is where $a = 0$, the desired value.
Further numerical/graphical experiments reveal that the distribution of the fractions seems to be uniform. While seeking further confirmation of this we have done the following, speaking in terms of (Delphi) Pascal:
program opnieuw;
procedure interval(var A,B : double); var h : double; begin A := Random; B := Random; if A > B then begin h := B; B := A; A := h; end; end;
procedure proef(r : double); const veel : integer = 1000000000; var x,l2,l3,lr,A,B : double; m,n,tel,t : integer; begin l2 := ln(2); l3 := ln(3); lr := ln(r); interval(A,B); A := -l3 + A*(l2+l3); B := -l3 + B*(l2+l3); m := 0; n := 0; tel := 0; t := 0; while tel < veel do begin x := m*l2 - n*l3 - lr; if x < 0 then m := m + 1 else n := n + 1; if (-l3 < x) and (x < +l2) then tel := tel + 1; if (A < x) and (x < B) then t := t + 1; end; Writeln((B-A)/(l2+l3),' = ',t/tel); end;
begin Random; Random; proef(1000); proef(0.001); proef(sqrt(2)); proef(1/sqrt(2)); while true do proef(Random); end.
Explanation. Make random intervals $\,]A,B[\,$ inside $\,]-\ln(3),+\ln(2)[\,$. The length of the latter interval is $\,\ln(3)+\ln(2)=\ln(6)\,$, the lenghs of the former are $\,(B-A)\,$. Count the (logarithms $x$ of the) fractions $\,(2^n/3^n)/r\,$ in both intervals. Let $N$ be the total number (tel) of iterands and $n$ be the number (t) of iterands in $\,]A,B[\,$. Then the distribution of the approximations $x$ is uniform if and only if: $$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$ Let's check. Output after a billion iterations each line:
6.58467502100393E-0001 = 6.58467500000000E-0001 3.98733151378110E-0001 = 3.98733149000000E-0001 1.56895805848762E-0001 = 1.56895804000000E-0001 5.34354087430984E-0002 = 5.34354050000000E-0002 4.04224734520540E-0001 = 4.04224734000000E-0001 2.33572337077931E-0001 = 2.33572341000000E-0001 4.06758418539539E-0001 = 4.06758418000000E-0001 1.46495995344594E-0001 = ....
But how can we prove that it is a uniform distribution?