Qualquer real positivo pode ser aproximado como $2^m/3^n$com $(m,n)$grande o suficiente?
Conjetura.
Existem inteiros positivos$(m,n)$grande o suficiente, tal que para qualquer número real positivo$r$e um dado erro$\epsilon$:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Há evidências numéricas para esta conjectura. eu tentei$r = \sqrt{2}$e$\epsilon = 10^{-3}$.
Abaixo está um pequeno programa Delphi Pascal com saída de acompanhamento.
Mas .. alguém pode provar a conjectura?
programa à parte;
procedimento teste(r : duplo; eps : duplo); var o dobro; m,n : inteiro; começar a := 1; m := 0; n := 0; enquanto é verdade começar se a < r então começar m := m + 1; a := a * 2; fim mais começo n := n + 1; a := a/3; fim; se abs(ra) < eps então Quebra; fim; Writeln(r,' = 2^',m,'/3^',n,' =',a); fim;
começar teste(sqrt(2),1.E-3); fim.
Saída:
1,41421356237310E+0000 = 2^243/3^153 = 1,41493657935359E+0000
ATUALIZAR.
A resposta de lhf parece uma prova muito concisa. Mas para mim - como físico aposentado por formação - está um pouco além da compreensão.
Além disso, deixa algumas questões intocadas. Pode-se perguntar, por exemplo, se existem estimativas para$m$e$n$quando$r$e$\epsilon$são dados.
Observação. A questão também pode ser formulada como: Qualquer real positivo pode ser aproximado como$3^m/2^n$com$(m,n)$grande o suficiente? O que é o mesmo que permitir inteiros negativos com a formulação original. Nesta forma, mostra alguma semelhança com o (in)famoso problema de Collatz .
EDITAR.
Conforme sugerido pelas respostas, uma abordagem com logaritmos poderia ser mais eficaz:
programa anders;
procedimento proef(r : double; eps : double); var a,l2,l3,lr : duplo; m,n : inteiro; começar l2 := ln(2); l3 := ln(3); lr := ln(r); a := 0; m := 0; n := 0; enquanto é verdade começar a := m*l2 - n*l3 - lr; se abs(a) < eps então Quebra; se a < 0 então m := m + 1 senão n := n + 1; fim; Writeln(r,' = 2^',m,'/3^',n,' =',exp(a)*r); fim;
começar proef(sqrt(2),1.E-3); proef(sqrt(2),1.E-9); fim.
Saída:
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$?
Respostas
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$.
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
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)\,$, os pontos preenchidos maciçamente pretos são as frações no processo de iteração, enquanto aumentam$m$e$n$com incrementos um de cada vez. O domínio de iterações é limitado por:$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. No nosso caso$r = 100$. Observe a sequência no início.
Portanto, parece que deve haver algumas frações próximas à linha vermelha, representando o número real$r$em questão.
Como podemos ter certeza disso? Vamos fazer um retrato da aglomeração das aproximações$a$no intervalo$\,]r/3,2r[\,$, escala logarítmica:$$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$A linha vermelha é onde$a = 0$, o valor desejado.
Outros experimentos numéricos/gráficos revelam que a distribuição das frações parece ser uniforme . Enquanto buscamos mais confirmação disso, fizemos o seguinte, falando em termos de (Delphi) Pascal:
abertura do programa;
intervalo de procedimento(var A,B : double); var h : duplo; começar A := Aleatório; B := Aleatório; se A > B então começar h := B; B := A; A := h; fim; fim;
procedimento prova(r : double); const veel : inteiro = 1000000000; var x,l2,l3,lr,A,B : duplo; m,n,tel,t : inteiro; começar l2 := ln(2); l3 := ln(3); lr := ln(r); intervalo(A,B); A := -l3 + A*(l2+l3); B := -l3 + B*(l2+l3); m := 0; n := 0; telefone := 0; t := 0; enquanto tel <veel faz começar x := m*l2 - n*l3 - lr; se x < 0 então m := m + 1 senão n := n + 1; se (-l3 < x) e (x < +l2) então tel := tel + 1; se (A < x) e (x < B) então t := t + 1; fim; Writeln((BA)/(l2+l3),' = ',t/tel); fim;
começar Aleatória; Aleatória; prova(1000); prova(0,001); prova(sqrt(2)); prova(1/sqrt(2)); enquanto é verdade prova(Aleatório); fim.
Explicação. Faça intervalos aleatórios$\,]A,B[\,$lado de dentro$\,]-\ln(3),+\ln(2)[\,$. A duração do último intervalo é$\,\ln(3)+\ln(2)=\ln(6)\,$, os comprimentos do primeiro são$\,(B-A)\,$. Conte os (logaritmos$x$das) frações$\,(2^n/3^n)/r\,$em ambos os intervalos. Deixar$N$ser o número total (tel) de iterands e$n$seja o número (t) de iterands em$\,]A,B[\,$. Então a distribuição das aproximações$x$é uniforme se e somente se:$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$Vamos checar. Saída após um bilhão de iterações em cada linha:
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 = ....
Mas como podemos provar que é uma distribuição uniforme?