Canadian traveller problem

2013-09-20T20:23:19Z

136.152.142.32: Adjacent edges -> incident edges

In [[number theory]], '''Lochs' theorem''' is a theorem concerning the rate of convergence of the [[continued fraction]] expansion of a typical real number. A proof of the theorem was published by [[Gustav Lochs]] in 1964.<ref>{{citation
| last = Lochs | first = Gustav
| doi = 10.1007/BF02993063
| journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
| language = German
| mr = 0162753
| pages = 142–144
| title = Vergleich der Genauigkeit von Dezimalbruch und Kettenbruch
| volume = 27
| year = 1964}}.</ref>

The theorem states that for [[almost all]] real numbers in the interval (0,1), the number of terms ''m'' of the number's continued fraction expansion that are required to determine the first ''n'' places of the number's decimal expansion behaves [[asymptotically]] as follows:

:<math>\lim_{n \rightarrow \infty} \frac{m}{n} = \frac {6 \ln 2 \ln 10}{ \pi^2} \approx 0.97027014</math> {{OEIS|id=A086819}}.<ref>{{MathWorld|urlname=LochsTheorem|title=Lochs' Theorem}}</ref>

As this limit is only slightly smaller than 1, this can be interpreted as saying that each additional term in the continued fraction representation of a "typical" real number increases the accuracy of the representation by approximately one decimal place. The [[decimal]] system is the last [[positional system]] for which each digit carries less information than one continued fraction quotient; going to [[Undecimal|base-11]] (changing <math>\ln 10</math> to <math>\ln 11</math> in the equation) makes the above value exceed 1.

The reciprocal of this limit,

:<math>\frac { \pi^2}{6 \ln 2 \ln 10} \approx 1.03064083</math> {{OEIS|id=A062542}},

is twice the base-10 logarithm of [[Lévy's constant]].

==References==
<references/>

[[Category:Continued fractions]]
[[Category:Theorems in number theory]]

formulasearchengine - User contributions [en]

Canadian traveller problem