Friday 22 March 2019

Champernowne constant

Yesterday, on the plane from Jakarta to Singapore, I was browsing The Story of Numbers by Mallik Asok Kumar and came across the following entry shown in Figure 1:

Figure 1: extract from page 114 of Mallik's The Story of Numbers


This struck a chord because earlier in the day, sitting in Starbuck's at Jakarta airport and analysing my number of the day (25554), I'd come across this entry in the Online Encyclopaedia of Integer Sequences (OEIS) shown in Figure 2:


Figure 2: OEIS A224896

What this meant was the sequence of digits 666666 occurs at position number 25554 in the decimal expansion of the Champernowne constant. Today, I had a look at the information contained in the Wikipedia entry for this topic. It explained that the Champernowne constant can be expressed as an infinite sequence:$$C_{m}=\sum_{n=1}^\infty\frac n{10_b^{~\left(\sum\limits_{k=1}^n\left\lceil\log_{10_b}(k+1)\right\rceil\right)}}$$where \(\lceil{x}\rceil = \)ceiling(\(x\)), \(10_b^{~x}=b^x\) in base 10, \(\log_{10_b}(x)=\log_{b_{10}}(x)\) and \(b\) is the base of the constant. However, a slightly different expression is given by Eric W. Weisstein (MathWorld):$$C_{m}=\sum_{n=1}^\infty\frac n{m^{\left(n+\sum\limits_{k=1}^{n-1}\left\lfloor\log_m(k+1)\right\rfloor\right)}}$$where \(\lfloor{x}\rfloor =\) floor function. I've no idea how these summations were arrived at but in order to determine positions listed in Figure 2, the SageMath code shown in Figure 4 can be used. The example shows the position of 88888888:

Figure 4: screenshot showing position of 88888888.
Click here to verify yourself in SageMathCell

Furthermore, the general name given to sequences like OEIS A224896 is the Earls Sequence, as explained in Figure 3.

Figure 3: The Earls Sequence showing the Champernowne constant
as well as other well known constants

Getting back to Champernowne's constant, its continued fraction expansion does not terminate (because it is not rational) and is aperiodic (because it is not an irreducible quadratic, Kurt Mahler having shown that the constant is transcendental). The terms in the continued fraction expansion exhibit very erratic behaviour, with extremely large terms appearing between many small ones e.g.
[0; 8, 9, 1, 149083, 1, 1, 1, 4, 1, 1, 1, 3, 4, 1, 1, 1, 15,
4 57540 11139 10310 76483 64662 82429 56118 59960 39397 10457 55500 06620 04393 09026 26592 56314 93795 32077 47128 65631 38641 20937 55035 52094 60718 30899 84575 80146 98631 48833 59214 17830 10987,
6, 1, 1, 21, 1, 9, 1, 1, 2, 3, 1, 7, 2, 1, 83, 1, 156, 4, 58, 8, 54, ... ]
To quote further from Wikipedia:
The large number at position 19 has 166 digits, and the next very large term at position 41 of the continued fraction has 2504 digits. The fact that there are such large numbers as terms of the continued fraction expansion is equivalent to saying that the convergents obtained by stopping before these large numbers provide an exceptionally good approximation of the Champernowne constant.

Tuesday 12 March 2019

Euler's Totient Function

From Wikipedia:
Euler's totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as φ(n) or ϕ(n), and may also be called Euler's phi function.
Today I turned 25545 days old and one of the points of interest about this number is that it forms a pair with 25546, both having the property that their totient values are the same (12480). The first member of the pairs of numbers with this property up to and including 25545 is given by OEIS A001274: numbers \(n\) such that \( \phi(n) = \phi(n+1) \):
1, 3, 15, 104, 164, 194, 255, 495, 584, 975, 2204, 2625, 2834, 3255, 3705, 5186, 5187, 10604, 11715, 13365, 18315, 22935, 25545
Note that for all prime numbers \(p\), \( \phi(p)=p-1 \). These totient values (totatives) represent the maximum possible for numbers up to \(p\) and their points lie on the maximal line as shown in Figure 1:


Figure 1: generated using SageMathCell using
plot(lambda x:euler_phi(int(x)), (x,1,100))

From Figure 1 it can be seen that the totient values (totatives) for 1 and 2, 3 and 4, 15 and 16 are the same. Note that 5186 and 5187 themselves form a pair, meaning that the totient values of 5186, 5187 and 5188 are the same (2592). This is the only triplet that occurs for numbers up to \( 10^{13} \).

Euler's totient function is a multiplicative function, meaning that if two numbers \(m\) and \(n\) are relatively prime, then \( \phi(m \times n) = \phi(m) \times \phi(n) \). This is important in developing Euler's product formula along with the fact that: $$\phi(p^k)=p^{k-1} \bigg (1-\frac{1}{p} \bigg )$$The product formula is: $$\phi(n)=n \prod_{p|n} \bigg (1-\frac{1}{p} \bigg )$$Applying this to today's number 25545=3 * 5 * 13 * 131, we note that:$$ \phi(25545) = 25545\bigg (1-\frac{1}{3} \bigg ) \bigg (1-\frac{1}{5} \bigg ) \bigg (1-\frac{1}{13} \bigg ) \bigg (1-\frac{1}{131} \bigg )=12480$$

Sunday 10 March 2019

Beyond Fibonacci

The Fibonacci sequence is the most famous example of a generalised sequence that begins with two seed numbers \( a \) and \( b \) and then proceeds as follows:$$ G_n=\begin{cases}a&\mbox{if }n=0;\\b&\mbox{if }n=1;\\G_{n-1}+G_{n-2}&\mbox{otherwise.}\end{cases} $$So \(G_3=b+a \), \(G_4=a+2b \) etc. It can be shown that the \(n\)-th term in the Fibonacci sequence is given by \( [ \phi ]^n/ \sqrt 5 \) (where the square brackets denote rounding to the nearest whole number) and so the question could be asked is there a general formula for calculating the \(n\)-th term of the generalised sequence \(a, b, a+b, a+2b, ... \)? Well, after watching this Numberphile video, it turns out that there is:


The formula is:$$G_n=\bigg [ \phi ^n \times \frac{(3 \sqrt 5 - 5) \, a + (5 - \sqrt 5) \, b}{10} \bigg ] $$When \(a=1\) and \(b=1\), we get \( [ \phi ]^n/ \sqrt 5 \) so all is well. When \(a=1 \) and \(b=3 \), we get simply \( [ \phi ]^n  \) and this generates the Lucas numbers: 1, 3, 4, 7, 11, ...

The Numberphile video makes the point that it is the number \( \sqrt 5 \) that is at the heart of this formula and thus underlies all these Fibonacci-like sequences that are generated from two seed numbers.

We can also consider not two but three seed numbers and this leads to what is called the Tribonacci sequence defined by:$$
T_n=\begin{cases}0&\mbox{if }n=0\\1&\mbox{if }n=1\\1&\mbox{if }n=2\\T_{n-1}+T_{n-2}+T_{n-3}&\mbox{if }n \geq 3\end{cases}

$$This leads to 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ... and, just as the closed-form formula for the Fibonacci sequence involved the roots of the polynomial \(x^2-x-1\), it is reasonable to expect that the analogous formula for the tribonacci sequence involves the polynomial \(x^3-x^2-x-1\) and this is indeed the case. This polynomial has one real root:$$ \frac{1}{3} \bigg ( 1+ \sqrt[3] {19+ 3 \, \sqrt {33}} + \sqrt[3] {19 -\sqrt {33}} \bigg ) \approx 1.83929 $$ called the tribonacci constant and this is the ratio of successive pairs of terms. In other words:$$

\lim_{n \to \infty} \frac {T_{n+1}}{T_n}=\frac{1}{3} \bigg ( 1+ \sqrt[3] {19+ 3 \, \sqrt {33}} + \sqrt[3] {19 -\sqrt {33}} \bigg ) \approx 1.83929

$$The other two roots are complex conjugates (source). The generating function for the tribonacci numbers is quite similar to the generating function for the Fibonacci numbers:$$ \sum_0 ^ \infty \! T_n \, x^n = \frac {x}{1-x-x^2-x^3} $$

Friday 8 March 2019

Vishwanath Number

I came across this interesting number in a book I was reading on Mathematics. To quote from pages 97 and 98 of The Story of Numbers by Mallick Asok Kumar:
This, almost certainly, irrational number has been discovered recently by an Indian computer scientist — named Divakar Vishwanath. This number is related to “Randomised Fibonacci Sequence”. Just like the normal Fibonacci sequence (see Section 2.6.1), the randomised version also starts with first two numbers as 1, 1. Thereafter one tosses a fair coin at every stage and use the following formula to generate the sequence:$$F_n=F_{n−2}±F_{n−1} \text{ for }n≥3$$The plus sign is used if the coin shows a head and the minus sign is used if the coin shows a tail. Vishwanath has proved that if you start to generate such avsequence, then, with probability 1, the absolute value of the \(N\)-th number in the randomised sequence will be approximately equal to the \(N\)-th power of 1.13198824 . . . . The bigger the value of \(N\), the closer is the absolute value of the \(N\)-th number of the randomised sequence to the \(N\)-th power of Vishwanath number 1.13198824 . . . . This number is almost certainly an irrational number.
Bear in mind that the recent discovery referred to in the above quote is now about twenty years old. Using SageMathCell, I tested this out for N=1000. Here is the code that I used:


The above box sometimes works but is temperamental. Here is a permalink to the code at SageMathCell. Some results are as follows (note that even though the \(N\)-th term can be very large, the \(N\)-th root of the number always reins it in:

71635048983737736457508495785347136900241837532880818653 1.13724785289546
-3868701952168426630626609949500693480141855962812452339 1.13393344608014
-230368470580308360353351991114643286077160535687 1.11522481150615
-1294461166539244845628908128250544767526170899091979974739663 1.14844999189994


Increasing \(N\) to 100,000 gives the following results:
  • 1.13104709702409
  • 1.13203489558527
  • 1.12848774540983
  • 1.13268434714159
Increasing \(N\) to 500,000 gives the following results:
  • 1.13181606331044
  • 1.13153973067764
  • 1.1312382520834
  • 1.13181595957100
Thus we see that, as \(N\) increases, the values draw closer to 1.13198824 . . . While the Vishwanath Number is "almost certainly an irrational number", one wonders whether or not it is a transcendental number. There's a more details report from March 1999 on this constant here and here is a quote in part from report:
To give some idea of what this result says, the way the randomized Fibonacci sequence is generated is a bit like the daily weather at a particular location. Today's weather can be assumed to depend on the weather the previous two days, but there is a large element of chance. The analog of the number 1.13198824 . . . for the weather would give a quantitative measure of the unpredictability of weather. It measures the rate at which small disturbances explode exponentially in time. It would tell you for exactly how many days high-speed computers can forecast weather reliably. Unfortunately, nobody knows this number for global weather, and probably never will. 
Viswanath's result brings to an end a puzzle that has its origins in 1960. In that year, Hillel Furstenberg (now at the Hebrew University) and Harry Kesten (at Cornell University) showed that for a general class of random-sequence generating processes that includes the random Fibonacci sequence, the absolute value of the \(N\)-th member of the sequence will, with probability 1, get closer to the \(N\)-th power of some fixed number. (The exact formulation of their result is in terms of random matrix products, and is not for the faint-hearted. See Viswanath's paper -- cited below -- for an exact statement, or read the whole story in the book Random Products of Matrices With Applications to Infinite-Dimensional Schrodinger Operators, by P. Bougerol and J. Lacroix, published by Birkhauser, Basel, in 1984.) 
Since Furstenberg and Kesten's deep result applied to the randomized Fibonacci process, it followed that, with probability 1, the absolute value of the Nth number in any random Fibonacci sequence will get closer and closer to the Nth power of some fixed number K. But no one knew the value of the number K, or even how to calculate it. 
What Viswanath did was find a way to compute \(K\). At least, he computed the first eight decimal places. Almost certainly, \(K\) is irrational, so cannot be computed exactly. Viswanath presented his new result at a colloquium at MSRI last month. 
Since there is no known algorithm to compute \(K\), Viswanath had to adopt a circuitous route, showing that \(K\) equals \(e^P\), where \(P\) lies somewhere between 0.1239755980 and 0.1239755995 (and, as usual, \(e\) is the base for natural logarithms). Since those two numbers are equal in their first eight decimal places, that meant he could calculate \(K\) to eight decimal places. 
The process involved large doses of mathematics and some heavy duty computing. Since his computation made use of floating point arithmetic -- which is not exact -- Viswanath had to carry out a detailed mathematical analysis to obtain an upper bound on any possible errors in the computation. He describes the key to his new result this way: "The problem was that fractals were coming in the way of an exact analysis. What I did was to guess the fractal and use it to find \(K\). To do this, I made use of some devilishly clever work carried out by Furstenberg in the early 1960s." 
And with that computation, mathematics has a new constant, a direct descendent of a pair of rabbits in thirteenth century Italy.
There's not been much on the Internet about Vishwanath's Number over the subsequent twenty years. The number did get a brief mention in another blog last year but that's about it. Nonetheless, it's an interesting concept.

Saturday 2 March 2019

Metallic Means

A Numberphile video on YouTube caught my attention recently. It was titled The Silver Ratio and I was prompted to investigate further.


I'll attempt to recapitulate what I discovered by watching this video and doing some additional investigation. The whole concept of Metallic Means is a generalisation of the Golden Mean. One way to approach matters is geometrically via the Golden Rectangle (Figure 1).
Figure 1: The Golden Rectangle
This rectangle has the property that \(a \div b=(a+b) \div a \) which can be rewritten as \( a^2=ab+b^2 \). Without loss of generality, we can simplify matters by letting \(b=1\) since it is the ratio that we are interested in and not any actual values of \(a\) and \(b\). This leads to \(a^2=a+1\) which can be rewritten as \( a^2-a-1=0 \). Solving this quadratic yields two solutions, one positive and one negative. Because we are dealing with positive lengths, we can ignore the negative solution. The positive solution is the familiar \( (1+\sqrt 5)/2 \) designated using the Greek letter \( \phi \). 

The equally famous Fibonacci spiral derives from the Golden Rectangle (Figure 2). If a square is removed from the rectangle, then the rectangle remaining is also a Golden Rectangle ad infinitum. The circular segments that can be inserted into each progressive square combine to form the spiral shown.

Figure 2: The Golden Spiral

The Silver Mean can be derived in a similar fashion from the so-called Silver Rectangle that has the dimensions shown in Figure 3. This rectangle has the property that \(a \div b=(2a+b) \div a \) which can be rewritten as \( a^2=2ab+b^2 \). Without loss of generality, we can again simplify matters by letting \(b=1\) and this leads to \(a^2=2a+1\) which can be rewritten as \( a^2-2a-1=0 \). Solving this quadratic yields two solutions, one positive and one negative. Because we are dealing with positive lengths, we can ignore the negative solution. The positive solution is \( (2+\sqrt 8)/2 \) which can be simplified to \( 1+\sqrt 2 \) and this is the Silver Mean or Silver Ratio. 

Figure 3: The Silver Rectangle

In the Silver Rectangle, removing two squares at a time leaves another rectangle of the same dimensions ad infinitum. The inscribed parts of the circles in the squares join together to form the characteristic spiral of the silver variety as shown in Figure 4.

Figure 4: The Silver Spiral

This process can be continued and what might be called the Bronze Rectangle is the result. Figure 5 is useful in comparing the relative dimensions of the Gold, Silver and Bronze Rectangles.

Figure 5: A comparison of the Golden, Silver and Bronze Rectangles

Looking at the progression of the numbers under the square root sign, it's immediately apparent that a Fibonacci progression is in play. The dimensions of the next rectangle would be \( (1+\sqrt 21)/2 \) and so on. Let's follow up on the Fibonacci connection by looking at the ratio of progressive pairs of terms in this sequence. The terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, ... and it's well known the ratio of progressive pairs of terms approaches the Golden Mean. If we write the \(n-th\) Fibonacci term as \(F_n\) then the relationship between terms is given by:$$ F_n=\begin{cases}0&\mbox{if }n=0;\\1&\mbox{if }n=1;\\F_{n-1}+F_{n-2}&\mbox{otherwise.}\end{cases} $$With the Silver Mean, the relationship is given by:$$ P_n=\begin{cases}0&\mbox{if }n=0;\\1&\mbox{if }n=1;\\2P_{n-1}+P_{n-2}&\mbox{otherwise.}\end{cases} $$This leads to the following sequence of terms: 0, 1, 2, 5, 12, 29, ... which is known as the Pell sequence. With the Bronze Mean, the relationship is given by: $$ T_n=\begin{cases}0&\mbox{if }n=0;\\1&\mbox{if }n=1;\\3T_{n-1}+T_{n-2}&\mbox{otherwise.}\end{cases} $$Here the progression of terms is: 0, 1, 3, 10, 33, 109, ... and so, in the most general case, we have a quadratic equation of the form \(a^2-k \times a -1 \) with positive solution \( (k+ \sqrt {k^2+4}) \div 2 \) and a relationship given by:$$ T_n=\begin{cases}0&\mbox{if }n=0;\\1&\mbox{if }n=1;\\k \times T_{n-1}+T_{n-2}&\mbox{otherwise.}\end{cases}$$where \(k\) is any integer greater than or equal to 1. So we've looked at the metallic means geometrically and in terms of Fibonacci-type sequences but they can also be looked at in terms of continued fractions. 

For the Golden Mean: \( (1+\sqrt 5) \div 2 \), the convergents are 2, 3/2, 5/3, 8/5, 13/8, 21/13, 34/21, 55/34, 89/55 ... and the continued fraction is:

1 + -------------------------------------------------
                              1                   
     1 + --------------------------------------------
                                 1                 
          1 + ---------------------------------------
                                   1               
               1 + ----------------------------------
                                      1           
                    1 + -----------------------------
                                        1         
                         1 + ------------------------
                                           1       
                              1 + -------------------
                                             1     
                                   1 + --------------
                                                1 
                                        1 + ---------
                                             1 + ...

For the Silver Mean: \( (2 + \sqrt 8) \div 2 \), the convergents are 5/2, 12/5, 29/12, 70/29, 169/70, 408/169, 985/408, 2378/985, 5741/2378, ... and the continued fraction is:

                            1                     
2 + -------------------------------------------------
                              1                   
     2 + --------------------------------------------
                                 1                 
          2 + ---------------------------------------
                                   1               
               2 + ----------------------------------
                                      1           
                    2 + -----------------------------
                                        1         
                         2 + ------------------------
                                           1       
                              2 + -------------------
                                             1     
                                   2 + --------------
                                                1 
                                        2 + ---------
                                             2 + ...

For the Bronze Mean: \( (3 + \sqrt 13 ) \div 2 \), the convergents are 10/3, 33/10, 109/33, 360/109, 1189/360, 3927/1189, 12970/3927, 42837/12970, 141481/42837, ... and the continued fraction is:

                            1                     
3 + -------------------------------------------------
                              1                   
     3 + --------------------------------------------
                                 1                 
          3 + ---------------------------------------
                                   1               
               3 + ----------------------------------
                                      1           
                    3 + -----------------------------
                                        1         
                         3 + ------------------------
                                           1       
                              3 + -------------------
                                             1     
                                   3 + --------------
                                                1 
                                        3 + ---------
                                             3 + ...


and so on and so on.