क्या किसी सकारात्मक वास्तविक का अनुमान लगाया जा सकता है? $2^m/3^n$ साथ से $(m,n)$ बहुत पर्याप्त?
अनुमान।
सकारात्मक पूर्णांक मौजूद हैं$(m,n)$ काफी बड़ा है, जैसे कि किसी भी सकारात्मक वास्तविक संख्या के लिए $r$ और एक त्रुटि दी $\epsilon$ : $$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$इस अनुमान के लिए संख्यात्मक प्रमाण हैं। मैने प्रयत्न किया$r = \sqrt{2}$ तथा $\epsilon = 10^{-3}$।
आउटपुट के साथ नीचे थोड़ा डेल्फी पास्कल कार्यक्रम है।
लेकिन .. क्या कोई अनुमान साबित कर सकता है?
कार्यक्रम के अलावा;
प्रक्रिया परीक्षण (आर: डबल; ईपीएस: डबल); वर एक डबल; एम, एन: पूर्णांक; शुरू a: = 1; m: = 0; n: = 0; जबकि सच है शुरू अगर एक आर तो शुरू m: = m + 1; a: = a * 2; अंत और शुरू n: = n + 1; a: = a / 3; समाप्त; अगर एब्स (आरए) <ईपीएस तो ब्रेक; समाप्त; रिटेलन (आर, '= 2 ^', मी, '/ 3 ^', एन, '=', ए); समाप्त;
शुरू परीक्षण (sqrt (2), 1.E-3); समाप्त।
आउटपुट:
1.41421356237310E + 0000 = 2 ^ 243/3 ^ 153 = 1.41493657935359E + 0000
अपडेट करें। Lhf
द्वारा उत्तर बहुत ही संक्षिप्त प्रमाण की तरह दिखता है। लेकिन मेरे लिए - शिक्षा द्वारा एक सेवानिवृत्त भौतिक विज्ञानी के रूप में - यह समझ से परे है। इसके अलावा, यह कुछ मुद्दों को अछूता छोड़ देता है। कोई उदाहरण के लिए पूछ सकता है कि क्या इसके लिए अनुमान हैं
$m$ तथा $n$ कब अ $r$ तथा $\epsilon$ दिया जाता है।
ध्यान दें। प्रश्न को इस रूप में भी प्रस्तुत किया जा सकता है: क्या किसी सकारात्मक वास्तविक का अनुमान लगाया जा सकता है$3^m/2^n$ साथ से $(m,n)$बहुत पर्याप्त? जो मूल सूत्रीकरण के साथ नकारात्मक पूर्णांक की अनुमति देने के समान है। इस रूप में, यह Collatz समस्या के लिए (में) की कुछ समानता दिखाता है ।
संपादित करें।
जैसा कि उत्तरों द्वारा सुझाया गया है, लॉगरिथम के साथ एक दृष्टिकोण अधिक प्रभावी हो सकता है:
प्रोग्रामर एंडर्स;
प्रक्रिया की प्रक्रिया (आर: डबल; ईपीएस: डबल); वर ए, एल 2, एल 3, एलआर: डबल; एम, एन: पूर्णांक; शुरू l2: = ln (2); l3: = ln (3); lr: = ln (r); a: = 0; m: = 0; n: = 0; जबकि सच है शुरू a: = m * l2 - n * l3 - lr; अगर एब्स (ए) <ईपीएस तो ब्रेक; अगर एक <0 तो m: = m + 1 और n: = n + 1; समाप्त; Writeln (r, '= 2 ^', m, '/ 3 ^', n, '=', exp (a) * r); समाप्त;
शुरू proef (sqrt (2), 1.E-3); proef (sqrt (2), 1.E-9); समाप्त।
आउटपुट:
1.41421356237310E + 0000 = 2 ^ 243/3 ^ 153 = 1.41493657935356E + 0000 1.41421356237310E + 0000 = 2 ^ 911485507/3 ^ 575083326 = 1.41421356125035E + 0000
आउटपुट में पहली पंक्ति पहले प्राप्त परिणाम के लगभग समान है।
आउटपुट में अंतिम पंक्ति से पता चलता है कि बाद वाला दृष्टिकोण वास्तव में अधिक प्रभावी है।
दोनों दृष्टिकोणों में त्रुटि एक ही भूमिका निभाती है। ओह ठीक है, लगभग। आइए एक नजर डालते हैं उन जगहों पर जहां 'ब्रेक हैं। पहला कार्यक्रम:$$ \left| r - \frac{2^m}{3^n} \right| < \epsilon $$ दूसरा कार्यक्रम: $$ -\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 $$ इसलिए $\epsilon$पहले कार्यक्रम में एक पूर्ण त्रुटि है, जबकि$\epsilon$दूसरे कार्यक्रम में एक रिश्तेदार त्रुटि है।
निरंतर कहानी:
क्या स्टर्न-ब्रोकोट पेड़ को बेहतर ढंग से संवारने के लिए नियोजित किया जा सकता है$2^m/3^n$?
जवाब
हां, हमेशा समाधान होते हैं $(m, n)$ किसी भी सकारात्मक वास्तविक के लिए $r$ तथा $\epsilon$ के लिये $$\left| r - \frac{2^m}{3^n} \right| < \epsilon$$और उन समाधानों को खोजने के लिए एक और अधिक कुशल तरीका है$m$ तथा $n$ एक-एक करके मान।
हमारे पास है $$r \approx 2^m/3^n$$ लघुगणक लेना, $$\log r \approx m\log 2 - n\log 3$$ $$\log r/\log 2\approx m - n\log 3 / \log 2$$ अर्थात, $$\log_2 r\approx m - n\log_2 3$$
[संयोग से, $$1 = \frac m{\log_2r}-\frac n{\log_3r}$$ जो एक पंक्ति है $(m,n)$ के साथ विमान $m$ अवरोधन $\log_2r$ तथा $n$ अवरोधन $-\log_3r$। हम यह जानना चाहते हैं कि यह रेखा पूर्णांक के करीब कब गुजरती है$(m, n)$ जाली अंक]।
हम उन आधार 2 लॉगरिथम को किसी भी सटीक परिशुद्धता के लिए तर्कसंगत अनुमान लगा सकते हैं। हालाँकि, पूर्णांक के साथ उस समीकरण को संतुष्ट करने के लिए $m$ तथा $n$हमारे सन्निकटन के हर को कम्यूटेट होना चाहिए।
लश्कर $$\log_2 r = f \approx s/t$$ तथा $$\log_2 3 \approx p/q$$ भिन्नों को सबसे कम शब्दों में, अर्थात $\gcd(s,t)=gcd(p,q)=1$।
फिर $$\frac st = m - n \frac pq$$ $$sq = (qm - pn)t$$ इस प्रकार $t|sq$। परंतु$s$ और $t$ मैथुन, इसलिए कर रहे हैं $t|q$।
लश्कर $q=tk$। $$f \approx \frac st = \frac{sk}{tk}=\frac{sk}{q}=\frac dq$$ कुछ पूर्णांक के लिए $d$।
तो, दिए गए सन्निकटन के लिए $\frac pq$ सेवा मेरे $\log_2 3$के लिए सबसे अच्छा तर्कसंगत सन्निकटन $f$ स्मारक के साथ भाजक हैं $\frac{d_0}q$ तथा $\frac{d_1}q$, कहां है $d_0=\lfloor fq\rfloor$ तथा $d_1=\lceil fq\rceil$। अर्थात्,$$\frac{d_0}q \le f \le \frac{d_1}q$$ अगर $f$ तर्कसंगत है (जैसे, जब $r=\sqrt 2$), तब फिर $d_0$ तथा $d_1$ बराबर हो सकता है।
तो किसी के लिए $p$ और $q$ हमें केवल पूर्णांक खोजने की आवश्यकता है $m$ और $n$ कि हमारे संशोधित समीकरण को हल करें $$\frac dq = m - n \frac pq$$ $$d=qm-pn$$ दोनों के लिए $d_0$ तथा $d_1$। किसी भी पूर्णांक के लिए समाधान हैं$d$ चूंकि $p$ और $q$मैथुन करते हैं। और उन समाधानों को विस्तारित यूक्लिडियन एल्गोरिथ्म का उपयोग करके पाया जा सकता है ।
लेकिन हमें उपयुक्त खोजने की भी जरूरत है $p$ और $q$। के निरंतर अंश विस्तार के अभिसरण का उपयोग करके किया जा सकता है$\log_2 3$। एक निरंतर अंश की गणना के लिए मानक एल्गोरिथ्म विस्तारित यूक्लिडियन एल्गोरिथ्म से निकटता से संबंधित है, और जैसा कि विकिपीडिया लेख बताता है (सिद्धांत 3 में), यदि$n$वें एक निरंतर अंश का अभिसरण है $\frac{h_n}{k_n}$ तब फिर $$k_nh_{n-1} - k_{n-1}h_n = (-1)^n$$ जो हमें खोजने में सक्षम बनाता है $m$ तथा $n$ एक अलग यूक्लिडियन एल्गोरिथ्म गणना किए बिना।
जारी रखा अंश अभिसरण $\frac hk$ एक नंबर का $x$ के लिए सबसे अच्छा तर्कसंगत सन्निकटन देता है $x$ किसी भी भाजक के लिए $\le k$। त्रुटि है$$\left|x - \frac hk\right| \le \frac 1{k^2}$$और यह अक्सर बहुत बेहतर हो सकता है। इसके विपरीत, एक सन्निकटन के लिए त्रुटि$\frac hk$ एक "यादृच्छिक" हर के साथ (यानी, एक निरंतर अंश अभिसरण नहीं) आम तौर पर चारों ओर है $\frac 1{2k}$।
दुर्भाग्य से, दो लघुगणक के लिए हमारे सन्निकटन में स्मारक की आवश्यकता के कारण, हम पूर्ण नहीं हैं $\frac 1{k^2}$अच्छाई। लेकिन हम आम तौर पर इससे बेहतर होते हैं$\frac 1{k}$।
तो दिए गए से बेहतर त्रुटि के साथ समाधान खोजने के लिए $\epsilon$, हम सिर्फ करने के लिए अभिसरण को देखने की जरूरत है $\log_2 3$ के पड़ोस में के साथ $\frac 1\epsilon$।
यहाँ कुछ ऋषि / पायथन कोड है जो उस कार्य को करता है। ऋषि लोकप्रिय पाइथन प्रोग्रामिंग भाषा के शीर्ष पर निर्मित गणितीय पुस्तकालयों का एक संग्रह है। इसमें मनमाने ढंग से सटीक अंकगणित है, और प्रतीकात्मक बीजगणित करने के लिए सुविधाएं हैं, लेकिन मैंने इस कोड में (ज्यादातर मनमानी परिशुद्धता अंकगणित के अलावा) ऋषि सुविधाओं से परहेज किया है, ताकि अन्य भाषाओं में पोर्ट करना आसान हो सके, यदि वांछित हो; मैंने एक समारोह से कई मूल्यों को वापस करने की क्षमता के अलावा, अधिकांश "पायथनिज़म" से भी बचा है।
# 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
यहाँ उस प्रोग्राम का आउटपुट है, जिसके साथ समाधान खोज रहे हैं $\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
और यहाँ एक लाइव संस्करण है जिसे आप SageMath सर्वर पर खेल सकते हैं। मेरा कोड सर्वर पर संग्रहीत नहीं है, यह URL में एन्कोडेड है।
यदि आपको छोटे के साथ अजीब व्यवहार मिलता है $\epsilon$, bitsवैश्विक चर (फ़ाइल के शीर्ष पर) की संख्या बढ़ाने का प्रयास करें । 53 की डिफ़ॉल्ट सेटिंग ठीक होनी चाहिए$\epsilon > 10^{-8}$या ऐसा। आपको depthनिरंतर अंश को बढ़ाने की भी आवश्यकता हो सकती है ।
FWIW, $\log_2 3$बल्कि समान रूप से तराजू के गणितीय संगीत सिद्धांत में महत्वपूर्ण है । मानक 12 टोन स्केल अभिसारी का उपयोग करता है$19/12$।
लश्कर $G= \mathbb Z \log 2 + \mathbb Z \log 3$। फिर$G$ का एक additive उपसमूह है $\mathbb R$। जबसे$\log 2 / \log 3$ तर्कहीन है, $G$चक्रीय नहीं हो सकता [1] और इसलिए घना होना चाहिए [२]। इसलिए,$\log r$ के तत्वों द्वारा मनमाने ढंग से सन्निकटन किया जाता है $G$।
[१] अगर $G = \mathbb Z \theta $, तब फिर $\log 2 = a \theta$ तथा $\log 3 = b \theta$ इसलिए $\log 2 / \log 3 = a/b $ तर्कसंगत है।
[२] देखें https://math.stackexchange.com/a/889775/589
एक अन्य प्रमाण के आंकड़े
लेम्मा 1.
अंश$2^m/3^n$ सभी के बीच हैं $r/3$ तथा $2r$।
सबूत।
कार्यक्रम के अनुसार - प्रश्न में प्रदर्शित किया गया है। से छोटा कोई भी अंश$r$ द्वारा गुणा किया जाता है $2$, तोह फिर $r.2$इन अंशों के लिए एक ऊपरी सीमा है। से बड़ा कोई अंश$r$ द्वारा विभाजित किया गया है $3$, तोह फिर $r/3$इन अंशों के लिए एक कम बाध्य है। जब पुनरावृत्तियों की शुरुआत होती है, तो कोई अन्य अंश नहीं हो सकता है।$$ r/3 < \frac{2^m}{3^n} < 2r $$ लेम्मा 2.
अनुक्रम में$2^m/3^n \to r$वहाँ कोई दो भिन्न समान हैं।
सबूत।
मान लीजिए कि हमारे पास है$2^{m_1}/3^{n_1} = 2^{m_2}/3^{n_2}$।
तीन मामलों में प्रतिष्ठित हैं:
- $m_1 \neq m_2$ तथा $n_1 = n_2$। फिर$2^{m_1} = 2^{m_2}$ इसलिये $m_1 = m_2$। अंतर्विरोध।
- $n_1 \neq n_2$ तथा $m_1 = m_2$। फिर$1/3^{n_1} = 1/3^{n_2}$ इसलिये $n_1 = n_2$। अंतर्विरोध।
- $m_1 \neq m_2$ तथा $n_1 \neq n_2$। तो हमारे पास हैं:$$ \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)} $$ परंतु $\,\ln(3)/\ln(2)\,$एक तर्कसंगत संख्या नहीं है। अंतर्विरोध।
इसलिए हमारे पास जो भिन्नताएं हैं, वे सभी भिन्न हैं, लेकिन उन्हें अंतराल के भीतर फिट होना चाहिए $\,]r/3,2r[\,$। इसका मतलब है कि अंशों में भीड़ हो जाती है। चलो पुनरावृत्ति प्रक्रिया, लघुगणक संस्करण की एक तस्वीर बनाते हैं। लाल रेखा द्वारा दिया गया है$\,\color{red}{\ln(3)y=\ln(2)x-\ln(r)}\,$, छोटे घेरे भिन्न होते हैं, ग्रिड पर मैप किए जाते हैं $\,m/n \to (m,n)\,$, बड़े पैमाने पर काले भरे डॉट्स वृद्धि की प्रक्रिया में भिन्न होते हैं $m$ तथा $n$एक समय में एक वेतन वृद्धि के साथ। पुनरावृत्तियों डोमेन द्वारा सीमित है:$\,\color{blue}{-\ln(2)\lt\ln(3)y-\ln(2)x+\ln(r)\lt\ln(3)}\,$। हमारे मामले में$r = 100$। शुरुआत में अनुक्रम को ध्यान में रखें।
तो ऐसा लगता है कि लाल रेखा के आस-पास कुछ भिन्नताएं होनी चाहिए, जिससे वास्तविक संख्या पुन: सक्रिय हो जाए $r$प्रश्न में।
हम इस बारे में कैसे सुनिश्चित हो सकते हैं? चलो सन्निकटन की भीड़ की तस्वीर बनाते हैं$a$ अंतराल में $\,]r/3,2r[\,$, लघुगणक मापक: $$ a = m\ln(2)-n\ln(3)-\ln(r) \quad \mbox{with} \quad -\ln(3) < a < \ln(2) $$ लाल रेखा जहां है $a = 0$वांछित मूल्य।
आगे के संख्यात्मक / चित्रमय प्रयोगों से पता चलता है कि अंशों का वितरण एक समान प्रतीत होता है । (डेल्फी) पास्कल:
कार्यक्रम opnieuw;
प्रक्रिया अंतराल (var ए, बी: डबल); वर एच: डबल; शुरू ए: = यादृच्छिक; बी: = यादृच्छिक; अगर ए> बी तो शुरू एच: = बी; बी: = ए; ए: = एच; समाप्त; समाप्त;
प्रक्रिया की प्रक्रिया (आर: डबल); स्थिरांक veel: पूर्णांक = 1000000000; वर x, l2, l3, lr, A, B: double; मी, एन, टेल, टी: पूर्णांक; शुरू l2: = ln (2); l3: = ln (3); lr: = ln (r); अंतराल (ए, बी); ए: =-एल 3 + ए * (एल 2 + एल 3); बी: =-एल 3 + बी * (एल 2 + एल 3); m: = 0; n: = 0; tel: = 0; t: = 0; जबकि tel <veel करते हैं शुरू x: = m * l2 - n * l3 - lr; अगर x <0 तो m: = m + 1 और n: = n + 1; if (-l3 <x) और (x <+ l2) तो tel: = tel + 1; अगर (A <x) और (x <B) तो t: = t + 1; समाप्त; Writeln ((BA) / (l2 + l3), '=', t / tel); समाप्त;
शुरू यादृच्छिक; यादृच्छिक; proef (1000); proef (0.001); proef (sqrt (2)); proef (1 / sqrt (2)); जबकि सच है proef (यादृच्छिक); समाप्त।
व्याख्या यादृच्छिक अंतराल करें$\,]A,B[\,$ के भीतर $\,]-\ln(3),+\ln(2)[\,$। बाद के अंतराल की लंबाई है$\,\ln(3)+\ln(2)=\ln(6)\,$, पूर्व की लेन हैं $\,(B-A)\,$। एक लघुगणक की गणना करें$x$ के) अंशों $\,(2^n/3^n)/r\,$दोनों अंतराल में। लश्कर$N$ iterands की कुल संख्या (tel) और हो $n$ में iterands की संख्या (टी) हो $\,]A,B[\,$। फिर सन्निकटन का वितरण$x$है वर्दी यदि और केवल यदि:$$ \lim_{N\to\infty}\frac{n}{N} = \frac{B-A}{\ln(6)} $$चलो देखते है। एक बिलियन पुनरावृत्तियों के बाद आउटपुट प्रत्येक पंक्ति:
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 = ...।
लेकिन हम यह कैसे साबित कर सकते हैं कि यह एक समान वितरण है?