Thursday, July 27, 2017

Golomb's Sequence



Golomb's sequence, named after Solomon Golomb, is a curious sequence of whole numbers that describes itself. It is defined in the following way: it is a non-decreasing sequence of whole numbers where the nth term gives the number of times n occurs in the sequence, and the first term is 1. From this we can begin constructing it: The second element must be greater than 1 as there is only one 1. It must be 2, and so must be the third element. Given this, there must be 2 threes, and from here on we may merely refer to the terms in the sequence and continue from there. The first several terms of the sequence are: \[ 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, \\ 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12,... \]

Recurrence Relation

The sequence can be given an explicit recurrence relation by stating it in the following way, using the self-describing property: To determine the next term in the sequence, go back the number of times that the previous term occurred (this will put you at the next-smallest value), then add one. For example, to determine the 12 term (6), count the number of times that the value of the 11th term (5) occurs (3 times). Step back that many terms (to the 9th term: 5) then add one to that value (6). This then gives the recurrence relation: \[ a(n+1)=1+a\left ( n+1-a(a(n)) \right ) \] Where \(a(1)=1\).

Asymptotic Behavior

The recurrence relation allows us to give an asymptotic expression for the value of the sequence. Let us suppose the sequence grows like \[ a(n)=A n^\alpha \] Let us put this into the recurrence relation: \[ A(n+1)^\alpha=1+A\left ( n+1-A(A n^\alpha)^\alpha \right )^\alpha \] Simplifying and rearranging, we obtain: \[ 1=\frac{1}{A(n+1)^\alpha}+\left (1-A^{1+\alpha}\frac{n^{\alpha^2}}{n+1} \right )^\alpha \] As \(\alpha<1\), \(\frac{n^{\alpha^2}}{n+1}\) goes to zero. For small x, \((1+x)^b\rightarrow 1+bx\). Thus, asymptotically: \[ 1\approx\frac{1}{A(n+1)^\alpha}+1-\alpha A^{1+\alpha}\frac{n^{\alpha^2}}{n+1} \] \[ \alpha A^{2+\alpha}n^{\alpha^2}(n+1)^{\alpha-1} \approx 1 \] Thus it must be the case that \[ \alpha^2+\alpha-1=0 \] \[ A=\alpha^{-\frac{1}{2+\alpha}} \] The solution to the first equation is \[ \alpha=\left \{\varphi-1,-\varphi \right \} \] Where \(\varphi\) is the golden ratio. As the exponent is clearly positive, we find the sequence is asymptotic to: \[ a(n)\rightarrow \varphi^{2-\varphi}n^{\varphi-1} \] Below we plot the ratio of these two expressions:

Friday, July 7, 2017

Continued Fractions


Definition and Background

A continued fraction is a representation of a number \(x\) in the form \[ x=a_0+\cfrac{b_0}{a_1+\cfrac{b_1}{a_2+\cfrac{b_2}{a_3+\cfrac{b_3}{\ddots}}}} \] Often, the b's are taken to be all 1's and the a's are integers. This is called the canonical or simple form. There are numerous ways of representing continued fractions. For instance, \[ x=a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\ddots}}}} \] can be represented as \[ x=a_0+\overset{\infty}{\underset{k=1}{\mathrm{K}}}\frac{1}{a_k} \] Or as \[ \left [ a_0;a_1,a_2,a_3,... \right] \]

Construction Algorithm

The continued fraction terms can be determined as follows: Given \(x\), set \(x_0=x\). Then \[ a_k=\left \lfloor x_k \right \rfloor \] \[ x_{k+1}=\frac{1}{x_k-a_k} \] Continue until \(x_k=a_k\).


The convergents of a continued fraction are the rational numbers resulting from taking the first n terms of the continued fraction. Let \(P_n\) and \(Q_n\) be the numerators and deominators respectively of the nth convergent (the one that includes \(a_n\)). It is not difficult to show that \[ P_n=a_nP_{n-1}+P_{n-2} \] \[ Q_n=a_nQ_{n-1}+Q_{n-2} \] An alternate way of saying this is that \[ \begin{bmatrix} a_n & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} P_{n-1} & Q_{n-1}\\ P_{n-2} & Q_{n-2} \end{bmatrix} = \begin{bmatrix} P_{n} & Q_{n}\\ P_{n-1} & Q_{n-1} \end{bmatrix} \] Where \[ \begin{bmatrix} P_{-1} & Q_{-1}\\ P_{-2} & Q_{-2} \end{bmatrix}= \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} \] And therefore \[ {}^L\prod^n_{k=0} \begin{bmatrix} a_k & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} P_{n} & Q_{n}\\ P_{n-1} & Q_{n-1} \end{bmatrix} \] Let \[p_n=\frac{P_n}{P_{n-1}}\] \[q_n=\frac{Q_n}{Q_{n-1}}\] Then \[p_n=a_n+\frac{1}{p_{n-1}}\] \[q_n=a_n+\frac{1}{q_{n-1}}\] We find that \[ \frac{P_{n+1}}{Q_{n+1}}=a_0+\sum_{k=0}^{n}\frac{(-1)^k}{Q_kQ_{k+1}} \] And thus \[ \left | x- \frac{P_{n}}{Q_{n}}\right |<\frac{1}{Q_nQ_{n+1}} \] As \(a_n \geq 1\), \(Q_n \geq F_n\) i.e. the nth Fibonacci number. This, then, implies Hurwitz's theorem: For any irrational number x, there exist infinitely many ratios \(P/Q\) such that \[ \left | x-\frac{P}{Q} \right |<\frac{k}{Q^2} \] Only if \(k \geq 1/\sqrt{5}\).

Periodic Continued Fractions

Suppose that for \(k \geq N\), \(a_{k+M}=a_k\). Let \[ [a_0;a_1,a_2,...a_{N-2}]=\frac{P_{Y1}}{Q_{Y1}} \] \[ [a_0;a_1,a_2,...a_{N-1}]=\frac{P_{Y2}}{Q_{Y2}} \] \[ \left [a_N;a_1,a_2,...a_{N+M-2} \right ]=\frac{P_{Z1}}{Q_{Z1}} \] \[ \left [a_N;a_1,a_2,...a_{N+M-1} \right ]=\frac{P_{Z2}}{Q_{Z2}} \] Then x satisfies the formula \[ x=\frac{P_{Y2}\cdot y+P_{Y1}}{Q_{Y2} \cdot y+Q_{Y1}} \] Where y satisfies \[ y=\frac{P_{Z2}\cdot y+P_{Z1}}{Q_{Z2} \cdot y+Q_{Z1}} \] Thus a continued fraction will be eventually periodic if and only if it is the solution of some quadratic polynomial.

Generic Continued Fractions

Let x be uniformly chosen between 0 and 1. We define a sequence of random variables as follows \[ \xi_0=x \] \[ \xi_{n+1}=\frac{1}{\xi_n}-\left \lfloor \frac{1}{\xi_n} \right \rfloor \] Clearly, if \[x=[0;a_1,a_2,a_3,...] \] Then \[\xi_n=[0;a_{n+1},a_{n+2},a_{n+3},...]\] Let us assume that, asymptotically, the \(\xi\)'s approach a single distribution. Based on our definitions, this would imply that \[ P(\xi_{n+1} < z)=\sum_{k=1}^{\infty} P \left (\frac{1}{k} < \xi_n < \frac{1}{k+z} \right ) \] Differentiating both sides gives the required relationship: \[ f_\xi(z)=\sum_{k=1}^{\infty}\frac{f_\xi\left ( \tfrac{1}{k+z} \right )}{(k+z)^2} \] Let us test the function \[ f_\xi(z)=\frac{A}{1+z} \] \[ \sum_{k=1}^{\infty}\frac{A}{1+\tfrac{1}{k+z}}\frac{1}{(k+z)^2}=\sum_{k=1}^{\infty}\frac{1}{(1+k+z)(k+z)} \] \[ \sum_{k=1}^{\infty}\frac{1}{(1+k+z)(k+z)}=\sum_{k=1}^{\infty}\frac{1}{k+z}-\frac{1}{k+z+1}=\frac{A}{1+z} \] It can be proved more rigorously that this is indeed the asymptotic probability density function, with \(A=1/\ln(2)\). Thus \[ P(\xi_{n} < z)=\log_2(1+z) \] From this we can easily find the asymptotic density function for the continued fraction terms. The probability that \(a_{n+1}=k\) is the same as the probability that \(\left \lfloor \tfrac{1}{\xi_n} \right \rfloor=k\). This is then \[ P(a_{n+1}=k)=P\left ( \frac{1}{k+1} < \xi_n \leq \frac{1}{k} \right )=\log_2(1+\tfrac{1}{k})-\log_2(1+\tfrac{1}{k+1}) \] \[ P(a_{n+1}=k)=\log_2\left ( \frac{(k+1)^2}{k(k+2)} \right )=\log_2\left ( 1+\frac{1}{k(k+2)} \right ) \] This is called the Gauss-Kuzmin Distribution.

From this we can then easily find the asymptotic geometric mean of the terms \[ \underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}a_k}=\exp\left (\underset{n \to \infty}{\lim} \frac{1}{n}\sum_{k=1}^{\infty} \ln(a_k)\right )=\exp\left ( E(\ln(a_k)) \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}a_k}= \exp\left (\sum_{j=1}^{\infty}P(a_k=j)\ln(j) \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}a_k}= \prod_{j=1}^\infty \left ( 1+\frac{1}{j(j+2)} \right )^{\log_2(j)}=2.685452001...=K_0 \] This value is called Khinchin's Constant.

Let us now look at the asymptotic behavior of the convergents. Namely, we wish to examine the asymptotic behavior of the denominators. First note that \[ \xi_n=\frac{1}{\xi_{n-1}}-a_n \] If we let \(y_n=1/\xi_n\), we then have \[ y_{n-1}=a_n+\frac{1}{y_n} \] From above we have that \[q_n=a_n+\frac{1}{q_{n-1}}\] As, asymptotically, \(\xi_n \sim \xi_{n-1}\), this implies that, asymptotically, \(y_n \sim y_{n-1} \sim 1/\xi_n\) and therefore \(q_n \sim q_{n-1} \sim 1/\xi_n\). Thus \[ f_q(z)=\left\{\begin{matrix} \frac{1}{z^2}\frac{1}{\ln(2)}\frac{1}{1+1/z} \\ 0 \end{matrix}\right.\; \; \begin{matrix} z > 1 \\ z \leq 1 \end{matrix} \] As \[ Q_n=\prod_{k=1}^{n}q_k \] We have \[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}=\underset{n \to \infty}{\lim}\sqrt[n]{\prod_{k=1}^{n}q_k}=\exp\left (\underset{n \to \infty}{\lim}\frac{1}{n}\sum_{k=1}^{\infty}\ln(q_k) \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}=\exp\left (E(\ln(q_n)) \right )= \exp\left (\int_{1}^{\infty}\ln(z)\frac{1}{z^2}\frac{1}{\ln(2)}\frac{1}{1+1/z}dz \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}= \exp\left (-\frac{1}{\ln(2)}\int_{0}^{1}\frac{\ln(z)}{1+z}dz \right ) \]\[ \underset{n \to \infty}{\lim}\sqrt[n]{Q_n}=\exp\left ( \frac{\pi^2}{12\ln(2)} \right )=3.275823... \] This value (or sometimes its natural log) is called Levy's constant.

We want to know how efficient continued fractions are for representing numbers relative to place-value expansions. Suppose we are working in base b. We want to find how many terms in the continued fraction expansion are required to obtain an approximation good to m base-b digits. We will have obtained such an approximation when the error is less than \(b^{-m}\) but greater than \(b^{-(m+1)}\). From above we have \[ \left | x- \frac{P_{n}}{Q_{n}}\right |<\frac{1}{Q_nQ_{n+1}} \] Thus \[ b^{-(m+1)} < \left | x- \frac{P_{n}}{Q_{n}}\right | < \frac{1}{Q_nQ_{n+1}} < \frac{1}{Q_n^2} \leq b^{-m} \] Rearranging, we have \[ b^m \leq Q_n^2 < b^{m+1} \] \[ b^{\frac{m}{2n}} \leq \sqrt[n]{Q_n} < b^{\frac{m+1}{2n}} \] Thus, as the center expression approaches a limit for large n, it follows that \(m/n\) does as well. Namely, by rearranging, we find that for n the number of continued fraction terms needed to express x in base b up to m decimal places, \[ \underset{m,n \to \infty}{\lim}\frac{m}{n}=\frac{\pi^2}{6\ln(2)\ln(b)} \] This is known as Loch's Theorem. In particular, for base 10, this implies that each continued fraction term provides on average 1.03064... digits of precision. In fact, base 10 is the largest integral base for which the continued fraction is more efficient.