Czy dowolna wartość rzeczywista dodatnia może być zbliżona jako $2^m/3^n$ z $(m,n)$ wystarczająco duży?
Przypuszczenie.
Istnieją liczby całkowite dodatnie$(m,n)$ wystarczająco duże, takie, że dla każdej dodatniej liczby rzeczywistej $r$ i dany błąd $\epsilon$ : $$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$Istnieją dowody na to liczbowa dla tego przypuszczenia. próbowałem$r = \sqrt{2}$ oraz $\epsilon = 10^{-3}$.
Poniżej znajduje się mały program Delphi Pascal z towarzyszącym wyjściem.
Ale… czy ktoś może udowodnić przypuszczenie?
program osobno;
procedura test(r : podwójny; eps : podwójny); var podwójny; m,n : liczba całkowita; zaczynać a := 1; m := 0; n := 0; podczas gdy prawda? zaczynać jeśli < r to zaczynać m := m + 1; a := a * 2; koniec inny początek n: = N + 1; a := a / 3; koniec; Jeśli ABS (RA) <EPS następnie break; koniec; Writeln(r,' = 2^',m,'/3^',n,' =',a); koniec;
zaczynać test(sqrt(2),1.E-3); koniec.
Wyjście:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935359E+0000
AKTUALIZACJA.
Odpowiedź lhf wygląda na bardzo zwięzły dowód. Ale dla mnie – jako emerytowanego fizyka z wykształcenia – jest to trochę niewyobrażalne.
Ponadto pozostawia kilka kwestii nietknięte. Można by zapytać na przykład, czy istnieją szacunki dla$m$ oraz $n$ Kiedy $r$ oraz $\epsilon$ są podane.
Notatka. Pytanie można również sformułować w następujący sposób: Czy dowolna liczba rzeczywista dodatnia może być aproksymowana jako$3^m/2^n$ z $(m,n)$wystarczająco duży? Jest to równoznaczne z dopuszczeniem ujemnych liczb całkowitych w oryginalnym sformułowaniu. W tej formie wykazuje pewne podobieństwo do (nie)sławnego problemu Collatza .
EDYTOWAĆ.
Jak sugerują odpowiedzi, bardziej efektywne może być podejście z logarytmami:
program anders;
procedura proef(r : double; eps : double); var a,l2,l3,lr : podwójny; m,n : liczba całkowita; zaczynać l2 := ln(2); 13 := ln(3); LR = ln (R); a := 0; m := 0; n := 0; podczas gdy prawda? zaczynać a := m*l2 - n*l3 - lr; Jeśli ABS (A) <EPS następnie break; jeśli a < 0 to m := m + 1 inaczej n := n + 1; koniec; Writeln(r,' = 2^',m,'/3^',n,' =',exp(a)*r); koniec;
zaczynać prof(sqrt(2),1.E-3); prof(sqrt(2),1.E-9); koniec.
Wyjście:
1.41421356237310E+0000 = 2^243/3^153 = 1.41493657935356E+0000 1.41421356237310E+0000 = 2^911485507/3^575083326 = 1.41421356125035E+0000
Pierwszy wiersz na wyjściu jest prawie identyczny z wynikiem uzyskanym poprzednio.
Ostatni wiersz w wynikach pokazuje, że to drugie podejście jest rzeczywiście bardziej efektywne.
Błąd odgrywa taką samą rolę w obu podejść. No cóż, prawie. Rzućmy okiem na miejsca, w których znajdują się 'Break's. Pierwszy program:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$ Drugi 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 $$ Więc $\epsilon$w pierwszym programie jest absolutny błąd, podczas gdy$\epsilon$w drugim programie jest błąd względny .
Ciąg dalszy na stronie:
Czy drzewo Sterna-Brocota może być wykorzystane do lepszej konwergencji?$2^m/3^n$?
Odpowiedzi
Tak, zawsze są rozwiązania $(m, n)$ za każdą pozytywną prawdę $r$ oraz $\epsilon$ dla $$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$I jest o wiele skuteczniejszy sposób na znalezienie tych rozwiązań niż przechodzenie dalej$m$ oraz $n$ wartości jeden po drugim.
Mamy $$r \approx 2^m/3^n$$ Logarytmowanie, $$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$ tj, $$\log_2 r\approx m - n\log_2 3$$
[Nawiasem mówiąc, $$1 = \frac m{\log_2r}-\frac n{\log_3r}$$ która jest linią w $(m,n)$ samolot z $m$ przechwycić $\log_2r$ oraz $n$ przechwycić $-\log_3r$. Chcemy dowiedzieć się, kiedy ta linia zbliża się do liczby całkowitej$(m, n)$ punkty sieci].
Możemy znaleźć racjonalne przybliżenia obu tych logarytmów o podstawie 2 z dowolną pożądaną dokładnością. Jednakże, w celu spełnienia tego równanie całkowitej $m$ oraz $n$mianowniki naszych przybliżeń muszą być współmierne.
Pozwolić $$\log_2 r = f \approx s/t$$ oraz $$\log_2 3 \approx p/q$$ z frakcjami będąc w najniższych kategoriach, czyli $\gcd(s,t)=gcd(p,q)=1$.
Następnie $$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$ Zatem $t|sq$. Jednak$s$ & $t$ są względnie pierwsze, stąd $t|q$.
Pozwolić $q=tk$. $$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$ dla jakiejś liczby całkowitej $d$.
Tak więc dla danego przybliżenia $\frac pq$ do $\log_2 3$, Najlepsze racjonalne przybliżenia $f$ z proporcjonalnymi mianownikami są $\frac{d_0}q$ oraz $\frac{d_1}q$, gdzie $d_0=\lfloor fq\rfloor$ oraz $d_1=\lceil fq\rceil$. To znaczy,$$\frac{d_0}q \le f \le \frac{d_1}q$$ Jeśli $f$ jest racjonalne (np. kiedy $r=\sqrt 2$), następnie $d_0$ oraz $d_1$ może być równy.
Więc dla danego $p$ & $q$ musimy tylko znaleźć liczby całkowite $m$ & $n$ które rozwiązują nasze zrewidowane równanie $$\frac dq = m - n \frac pq$$ $$d=qm-pn$$ dla obu $d_0$ oraz $d_1$. Istnieją rozwiązania dla dowolnej liczby całkowitej$d$ bo $p$ & $q$są względnie pierwsze. A te rozwiązania można znaleźć za pomocą rozszerzonego algorytmu euklidesowego .
Ale musimy też znaleźć odpowiedni $p$ & $q$. Można to zrobić za pomocą zbieżności ciągłego rozszerzania ułamka$\log_2 3$. Standardowy algorytm obliczania ułamka łańcuchowego jest ściśle powiązany z rozszerzonym algorytmem euklidesowym i jak wyjaśnia ten artykuł w Wikipedii (w Twierdzeniu 3), jeśli$n$-ta zbieżność ułamka łańcuchowego to $\frac{h_n}{k_n}$ następnie $$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$ co pozwala nam znaleźć $m$ oraz $n$ nie robiąc osobną kalkulację Algorytm Euklidesa.
Ciągła zbieżność frakcji $\frac hk$ liczby $x$ daje najlepsze racjonalne przybliżenia do $x$ dla dowolnego mianownika $\le k$. Błąd jest$$\left|x - \frac hk\right| \le \frac 1{k^2}$$i często może być znacznie lepiej. W przeciwieństwie do tego błędu aproksymacji$\frac hk$ z mianownikiem „losowym” (tj. nie zbieżnym ułamkiem ciągłym) jest ogólnie około $\frac 1{2k}$.
Niestety, ze względu na potrzebę współmiernych mianowników w naszych przybliżeniach do dwóch logarytmów, nie otrzymujemy pełnej $\frac 1{k^2}$dobroć. Ale generalnie robimy się lepsi niż$\frac 1{k}$.
Tak, aby znaleźć rozwiązania o lepszej błędu niż dana $\epsilon$, wystarczy spojrzeć na zbieżności, aby $\log_2 3$ z mianownikami w sąsiedztwie $\frac 1\epsilon$.
Oto kod Sage/Python, który wykonuje to zadanie. Sage to zbiór bibliotek matematycznych zbudowanych na popularnym języku programowania Python. Ma arytmetykę arbitralnej precyzji i udogodnienia do wykonywania algebry symbolicznej, ale (w większości) unikałem funkcji Sage w tym kodzie (oprócz arytmetyki arbitralnej precyzji), aby w razie potrzeby ułatwić przeniesienie do innych języków; Unikałem również większości "pytonizmów", poza zdolnością Pythona do zwracania wielu wartości z funkcji.
# 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
Oto wynik tego programu, szukający rozwiązań za pomocą $\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
A oto wersja na żywo , z którą możesz grać na serwerze SageMath. Mój kod nie jest przechowywany na serwerze, jest zakodowany w adresie URL.
Jeśli zachowujesz się dziwnie z małym $\epsilon$, spróbuj zwiększyć numer bitszmiennej globalnej (na górze pliku). Domyślne ustawienie 53 powinno być w porządku dla$\epsilon > 10^{-8}$lub tak. Może być również konieczne zwiększenie depthułamka kontynuacyjnego.
FWIW, $\log_2 3$jest raczej ważne w matematycznej teorii muzyki o skalach równomiernie temperowanych . Standardowa 12-tonowa skala wykorzystuje zbieżny$19/12$.
Pozwolić $G= \mathbb Z \log 2 + \mathbb Z \log 3$. Następnie$G$ jest podgrupą addytywną $\mathbb R$. Od$\log 2 / \log 3$ jest irracjonalne, $G$nie może być cykliczny [1] i musi być gęsty [2]. W związku z tym,$\log r$ jest arbitralnie aproksymowana przez elementy $G$.
[1] Jeśli $G = \mathbb Z \theta $, następnie $\log 2 = a \theta$ oraz $\log 3 = b \theta$ a więc $\log 2 / \log 3 = a/b $ jest racjonalne.
[2] Patrz https://math.stackexchange.com/a/889775/589
Heurystyka innego dowodu
Lemat 1.
Ułamki$2^m/3^n$ są wszystkie pomiędzy $r/3$ oraz $2r$.
Dowód.
Zgodnie z programem - jak pokazano w pytaniu. Dowolny ułamek mniejszy niż$r$ jest pomnożone przez $2$, więc $r.2$to górna granica dla tych ułamków. Dowolny ułamek większy niż$r$ dzieli się przez $3$, więc $r/3$jest dolną granicą dla tych ułamków. Nie może być innych ułamków, z wyjątkiem momentu rozpoczęcia iteracji.$$ r/3 < \frac{2^m}{3^n} < 2r $$ Lemat 2.
W sekwencji$2^m/3^n \to r$nie ma dwóch takich samych ułamków.
Dowód.
Załóżmy, że mamy$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$.
Rozróżnia się trzy przypadki:
- $m_1 \neq m_2$ oraz $n_1 = n_2$. Następnie$2^{m_1} = 2^{m_2}$ W związku z tym $m_1 = m_2$. Sprzeczność.
- $n_1 \neq n_2$ oraz $m_1 = m_2$. Następnie$1/3^{n_1} = 1/3^{n_2}$ W związku z tym $n_1 = n_2$. Sprzeczność.
- $m_1 \neq m_2$ oraz $n_1 \neq n_2$. Potem będzie:$$ \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)} $$ Jednak $\,\ln(3)/\ln(2)\,$nie jest liczbą wymierną. Sprzeczność.
Mamy więc kilka ułamków, wszystkie różne, ale muszą mieścić się w przedziale $\,]r/3,2r[\,$. Oznacza to, że frakcje stają się zatłoczone. Zróbmy obraz procesu iteracji w wersji logarytmicznej. Czerwona linia jest podana przez$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, małe kółka to ułamki, odwzorowane na siatce $\,m/n \to (m,n)\,$, masowo czarne wypełnione kropki to ułamki w procesie iteracji, podczas gdy wzrastają $m$ oraz $n$z przyrostami pojedynczo. Domena iteracji jest ograniczona przez:$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$. W naszym przypadku$r = 100$. Uważaj na sekwencję na początku.
Wygląda więc na to, że w pobliżu czerwonej linii musi znajdować się sporo ułamków reprezentujących liczbę rzeczywistą $r$w pytaniu.
Jak możemy być tego pewni? Zróbmy obraz natłoku przybliżeń$a$ w przedziale $\,]r/3,2r[\,$, skala logarytmiczna: $$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$ Czerwona linia jest gdzie $a = 0$, żądaną wartość.
Dalsze eksperymenty numeryczne/graficzne pokazują, że rozkład frakcji wydaje się być równomierny . Szukając dalszego potwierdzenia tego, zrobiliśmy co następuje, mówiąc w kategoriach (Delphi) Pascal:
program opnieuw;
interwał procedury(var A,B : double); var h : podwójne; zaczynać A := Losowo; B := Losowo; jeśli A > B to zaczynać h := B; B := A; A := h; koniec; koniec;
procedura prof(r : podwójna); stały welon : liczba całkowita = 1000000000; var x,l2,l3,lr,A,B : podwójne; m,n,tel,t : liczba całkowita; zaczynać l2 := ln(2); 13 := ln(3); lr := ln(r); interwał(A,B); A := -13 + A*(l2+13); B := -13 + B*(l2+13); m := 0; n := 0; tel := 0; t := 0; podczas gdy tel < veel do zaczynać x := m*l2 - n*l3 - lr; jeśli x < 0 to m := m + 1 inaczej n := n + 1; jeśli (-l3 < x) i (x < +l2) to tel := tel + 1; jeśli (A < x) i (x < B) to t := t + 1; koniec; Writeln((BA)/(l2+13),' = ',t/tel); koniec;
zaczynać Losowy; Losowy; dowód (1000); dowód (0,001); profesor(sqrt(2)); prof.(1/sqrt(2)); podczas gdy prawda? dowód (losowy); koniec.
Wyjaśnienie. Twórz losowe interwały$\,]A,B[\,$ wewnątrz $\,]-\ln(3),+\ln(2)[\,$. Długość tego ostatniego przedziału wynosi$\,\ln(3)+\ln(2)=\ln(6)\,$, długości tych pierwszych są $\,(B-A)\,$. Policz (logarytmy$x$ z) frakcji $\,(2^n/3^n)/r\,$w obu interwałach. Pozwolić$N$ być całkowitą liczbą (tel) iterandów i $n$ być liczbą (t) iterandów w $\,]A,B[\,$. Następnie rozkład przybliżeń$x$jest jednolity wtedy i tylko wtedy, gdy:$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$Sprawdźmy. Dane wyjściowe po miliardach iteracji w każdym wierszu:
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 = ....
Ale jak udowodnić , że jest to rozkład równomierny?