Thue-Morse Constant

On June 20th 2020, I made a post titled Prouhet-Thue-Morse Sequence named for Eugène Prouhet, Axel Thue, and Marston Morse (the Prouhet reference is sometimes omitted). By the way, the Thue part is named after Axel Thue, whose name is pronounced as if it were spelled "Tü" where the ü sound is roughly as in the German word üben. It is incorrect to say "Too-ee" or "Too-eh". Thus sayeth N. J. A. Sloane, June 12th 2018, in his comments about OEIS A010060 that lists the members of the sequence. 

It is a most interesting sequence and my blog post covers it quite well and has links to three interesting YouTube videos. However, there is a so-called Thue-Morse constant that is the topic of this post. The sequence begins:

 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, ... 

If we concatenate these binary digits, we get a binary number:

 \(P=0.0110100110010110100101100..._2\) 

This number can be converted a decimal and is represented by the Greek letter \( \tau \):$$\tau=\sum_{n=0}^{\infty} \frac{t_i}{2^{i+1}}=0.4124540336401075977 \dots$$where \(t_i\) is the \(i^{th}\) element of the binary Thue-Morse sequence. The number has been shown to be transcendental.

Figure 1 provides two interesting expressions for the Thue-Morse constant (source):

Figure 1

I came across the constant by means of my diurnal age investigation, discovering that the number associated with my diurnal age (26547) was a member of OEIS A096394:

A096394

Engel expansion of Thue-Morse constant.

The sequence begins 3, 5, 6, 9, 12, 19, 92, 173, 242, 703, 1861, 3186, 4746, 7843, 26547, ... and the comments state that:$$ 0.4124540336 \dots = \frac{1}{3}+\frac{1}{3 \times 5}+\frac{1}{3 \times 5 \times 6}+\frac{1}{3 \times 5 \times 6 \times 9} + \dots$$I made a post about Engel Expansions way back on September 28th 2016.

If we take 0.412454033640107597783361368258455283089 as an approximation of \(\tau\) and plug this into the SageMathCell formula listed in this post, we do confirm that 26547 is a member. To generate further members of the sequence however, the number of decimal places to which \( \tau \) needs to be approximated must be increased. Here is a permalink to SageMathCell while the code is listed below (blue for input and red for output).

x=0.412454033640107597783361368258455283089

u=x

E=[1]

F=[]

product=1

sum=0

for i in [1..15]:

    a=ceil(1/u)

    u=u*a-1

    E.append(a)

    product=product*a

    sum+=1/product

    F.append(1/product)

print(E, "... this is the Engels expansion")

[1, 3, 5, 6, 9, 12, 19, 92, 173, 242, 703, 1861, 3186, 4746, 7843, 26547] ... this is the Engels expansion

The Greedy Algorithm

I started browsing a book by David Wells called The Penguin Book of Curious and Interesting Puzzles. The first book that I encountered by this author was Prime Numbers:  The Most Mysterious Figures in Math and it is a most interesting book. A brief biography at the start of the this Penguin book informs us that:

David Wells was born in 1940. He had the rare distinction of being a Cambridge scholar in mathematics and failing his degree. He subsequently trained as a teacher and, after working on computers and teaching machines, taught mathematics and science in a primary school and mathematics in secondary schools. He is still involved with education through writing and working with teachers. While at university he became British under-21 chess champion, and in the mIddle seventies was a game inventor, devising 'Guerilla' and 'Checkpoint Danger', a puzzle composer, and the puzzle editor of Games & Puzzles magazine. From 1981 to 1983 he published The Problem Solver, a magazine of mathematical problems for secondary pupils. He has published several books of problems and popular mathematics, including Can You Solve These? and Hidden Connections, Double Meanings, and also Russia and England, and the Transformations of European Culture. He has written The Penguin Dictionary of Curious and Interesting Numbers and The Penguin Dictionary of Curious and Interesting Geometry, and is currently writing a book on the nature, learning and teaching of mathematics.

One of the first topics he deals with is Egyptian Fractions which consist only of unit fractions, meaning fractions with a numerator of 1. For example, the Egyptians would have expressed the fraction \( \frac{7}{10} \) as \( \frac{1}{2}+ \frac{1}{5} \).

The author then asks the question: 

Can all proper fractions be expressed as the sum of unit fractions, without repetition? 

The answer is: 

Yes, as Fibonacci showed, also in his Liber Abaci, where he described what is now called the greedy algorithm. Subtract the largest possible unit fraction, then do the same again, and so on. Sylvester proved in 1880 that applying this greedy algorithm to the fraction \( \frac{p}{q} \), where \(p\) is less than \(q,\) produces a sequence of no more than \(p\) unit fractions.

The site CODESDOPE provides the Python code to generate an Egyptian fraction from an improper fraction. Here is the code, applied to the fraction \( \frac{5}{7} \), together with its output:

import math

unit_den_array = [0]*10

iter = 0

def gcd(a, b):

  c = a%b

  while(c > 0):

    a = b

    b = c

    c = a % b

  return b

def greedy_egyptian_fraction(num, den):

  global iter

  if(num == 1):

    #appending list unit_den_array

    iter = iter+1 # storing in unit_den_array from index 1 not 0

    unit_den_array[iter] = den

  else:

    unit_den = math.ceil(den/num)

    iter = iter+1

    unit_den_array[iter] = unit_den

    gcd_of_numbers = gcd((num*unit_den) - den, den*unit_den)

    greedy_egyptian_fraction(((num*unit_den) - den)//gcd_of_numbers, (den*unit_den)//gcd_of_numbers)

if __name__ == '__main__':

  greedy_egyptian_fraction(5, 7)

  for i in range(1, iter+1):

    print(unit_den_array[i])

2

5

70

There is a lot of code and the contrast with the amount of code needed for SageMath could not be more stark. Here is code required for SageMath to accomplish exactly the same task:

L=[]

n=5/7

while n>0:

    bottom=ceil(denominator(n)/numerator(n))

    L.append(bottom)

    n=n-1/bottom

print(L)

[2, 5, 70]

While I am inclined to become more proficient in the use of Python, I am at the same time aware of how much more SageMath is suited to performing mathematical tasks, as the example of Egyptian fractions illustrate. Why go through a painful Python procedure to generate an outcome that SageMath can achieve almost effortlessly. It took me a few minutes to generate the SageMath code but I'm sure I would have struggled for much longer if I had only Python code to rely on. Here is the permalink to SageMathCell.

As the CODESDOPE observes in Figure 1:

Figure 1

My SageMath algorithm has provided the first representation but not the second. The latter is preferable in one way because the maximum denominator is much smaller (21 versus 70). Another way to generate an Egyptian fraction is by determining the Engel expansion for the proper fraction. I posted about the Engel expansion on the 26th September 2016. For an explanation of what this expansion is all about, see Figure 2.

Figure 2

The algorithm I developed to generate the Engel expansion for any positive real number is shown below, using \( \frac{5}{7} \) as an example (permalink):

x=5/7

u=x

E=[1]

F=[]

product=1

sum=0

for i in [1..10]:

    if u==0:

        break

    else:

        a=ceil(1/u)

    u=u*a-1

    E.append(a)

    product=product*a

    sum+=1/product

    F.append(1/product)

print("Engel expansion is",E)

print("Fraction expression is",F)

Engel expansion is [1, 2, 3, 4, 7]

Fraction expression is [1/2, 1/6, 1/24, 1/168]

So additionally \( \frac{5}{7}= \frac{1}{2}+ \frac{1}{6}+ \frac{1}{24}+ \frac{1}{168} \). Interestingly, I discovered on this website about proper fractions of the form \( \frac{4}{n} \) and \( \frac{3}{n} \). To quote from the site:

In the 1940s, the mathematicians Paul Erdos and Ernst G. Straus conjectured that every fraction with numerator = 4 can be written as an Egyptian fraction sum with three terms. If you have found an example that appears to need more than three, can you find an alternative sum? Can you find a reason why it must work, or a counter-example - the conjecture isn't yet proved. It is proved for \( \frac{3}{n} \).

Testing this out on \( \frac{3}{7} \), we find an Egyptian fraction of \( \frac{1}{3}+ \frac{1}{11}+\frac{1}{231}\). I'm sure there's a lot more that can be said about Egyptian fractions but I'll finish up here and maybe return to the topic at a later date. Figure 3 shows how the Egyptians connected the senses with fractions that had powers of 2 as denominators.

Figure 3

It can be noted that \( \frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{32}+\frac{1}{64}=\frac{63}{64}\)

Apéry's Constant

Today I turned 25355 days old and this number turns up in the Engel expansion of \( \zeta(3) \). Firstly however, let's remind ourselves that \( \zeta \) is the Riemann zeta function and can be expressed as:$$ \zeta(3)=\sum_1^{\infty} \frac{1}{n^3} $$ $$ \text{or  } \zeta(3)=\lim_{n \rightarrow \infty} \left( \frac{1}{1^3}+\frac{1}{2^3}+ \cdots + \frac{1}{n^3} \right) $$This works out to around 1.202056903159594285399738161511449990764986292 and is known as Apèry's constant. I've written about this constant before in a post titled The Basel Problem and Beyond on May 7th 2017. According to Wikipedia:

This constant arises naturally in a number of physical problems, including in the second-and third-order terms of the electron's gyromagnetic ratio using quantum electrodynamics. It also arises in the analysis of random minimum spanning trees and in conjunction with the gamma function when solving certain integrals involving exponential functions in a quotient which appear occasionally in physics, for instance when evaluating the two-dimensional case of the Debye model and the Stefan–Boltzmann law.

This doesn't mean much to me but there you have it. As for the Engel expansion, I made a blog post about it in 2016. The expansion consists of the terms that go to make up the denominators of the fractions that when added will approximate \( \zeta(3) \). OEIS A053980 lists the first few terms as: 1, 5, 98, 127, 923, 5474, 16490, 25355

A053980

Engel expansion of zeta(3) = 1.20206...

This means that \( \zeta(3) \) can be approximated as:$$ \zeta(3) \approx \frac{1}{1}+\frac{1}{1 \times 5} +\frac{1}{1 \times 5 \times 98}+\frac{1}{1 \times 5 \times 98 \times 127} +\frac{1}{1 \times 5 \times 98 \times 127} + \cdots $$Of course, once the zeta function is touched upon, one can find oneself in very deep water very quickly so I'm not going to say too much more except to include a screenshot (Figure 1) from Wolfram MathWorld showing the Engel expansions for some of the other constants:

Figure 1

The SAGE code for generating these sequences is fairly straightforward. Figure 2 shows what's involved for Apèry's constant:

Figure 2: permalink

Of course, simply replacing u in the above code by say \(e\) or \(\pi \) will produce the associated Engel expansion.

on May 12th 2021

Engel Expansions

I've encountered Engel expansions before and today I was reminded of them again when my day count number, 24648, featured in OEIS A068379 as the Engel expansion of sinh(1/2). The initial sequence of numbers is:

1, 24, 80, 168, 288, 440, 624, 840, 1088, 1368, 1680, 2024, 2400, 2808, 3248, 3720, 4224, 4760, 5328, 5928, 6560, 7224, 7920, 8648, 9408, 10200, 11024, 11880, 12768, 13688, 14640, 15624, 16640, 17688, 18768, 19880, 21024, 22200, 23408, 24648, 25920, 27224

An Engel expansion is explained by Wikipedia as:

The algorithm for calculating the terms in an Engels expansion is as follows:

This is straightforward enough and I set up a worksheet in Excel to calculate the terms of the Engel expansion for whatever number I entered. I tested it out and all seemed well until I looked more closely at the terms I got for sinh(1/2). Here they are as reported by the worksheet:

The first six terms match the OEIS listing but the seventh diverges by one (623 as opposed to 624) and after that things rapidly fall apart as can be seen by comparing terms. I guess the slight errors that arise as the increasingly smaller u-th terms are divided into one quickly compound and spell disaster. Interesting illustration of the limitations of spreadsheets when very small numbers are concerned.

ADDENDUM:

It's now 1st May 2019 and I've been using SageMath for quite some time now. Here is the SageMath code to generate the Engels expansion of sinh(1/2) up to 24648 (permalink to SageMathCell):

[1, 2, 24, 80, 168, 288, 440, 624, 840, 1088, 1368, 1680, 2024, 2400, 2808, 3248, 3720, 4224, 4760, 5328, 5928, 6560, 7224, 7920, 8648, 9408, 10200, 11024, 11880, 12768, 13688, 14640, 15624, 16640, 17688, 18768, 19880, 21024, 22200, 23408, 24648]