ODD + and EVEN - Improved Format

Some time ago I got Gemini to carry out an analysis for me of attractors and vortices in the range up to 40000 under the ODD + and EVEN - algorithm. I copied the output into a Google document that listed: 

• each attractor and how many captives it had
• each vortex (along with the vorticals that comprised it)
• the number of captives the vortex had

Here is the information the 193 page document displays for the attractor 39642:

• Attractor: 39642
• Captive Count: 395
• Captives: [38997, 39017, 39035, 39037, 39039, 39053, 39055, 39059, 39063, 39065, 39070, 39071, 39072, 39073, 39074, 39075, 39076, 39077, 39078, 39083] ... (and 375 more)

Here is the information the documents displays for the vortex [38013, 38012, 38006, 37995, 38028]:

• Vortex (Vorticals): [38013, 38012, 38006, 37995, 38028]
• Captive Count: 564
• Captives: [37055, 37075, 37097, 37099, 37107, 37123, 37125, 37127, 37133, 37135, 37137, 37139, 37141, 37143, 37145, 37149, 37150, 37151, 37152, 37153] ... (and 544 more)

The attractors and vortices are arranged in descending order by number of captives. The information is readily accessible but I thought I'd use Gemini again to improve the formatting of the document to make it more readable. Figure 1 shows the opening page of the 137 page document and Figure 2 shows the second page.

Figure 1

Figure 2

The document lists the attractors in ascending order and also in descending order by number of captives (see Tables 1 and 2 for the start of each table).

Table 1

Table 2

The document goes on to list vortices in ascending order and also in descending order by number of captives (see Tables 3 and 4):

Table 3

Table 4

Overall the document provides an excellent organisation of the data and I'll roll this out this the results for the ODD - and EVEN + algorithm and the PRIME + NON-PRIME - algorithm in the near future.

Linear Recurrence Revisited

It's been a while since I posted about linear recurrence relations. The only two posts were:

• Solving Linear Recurrence on the 16th of June 2020
  
• More on Linear Recurrence on the 26th December 2020

Today I turned \(28073\) days old and one of the properties of this number is that it's a member of OEIS A105578:$$ \begin{align}  &\text{a}(n+3) = 2\text{a}(n+2) - 3\text{a}(n+1) + 2\text{a}(n)\\ &a(0) = 1, a(1) = 1, a(2) = 0 \end{align}$$This linear recurrence of order 3 corresponds to the cubic equation:$$ \begin{align} &x^3 = 2x^2 -3x +2 \\ &x^3-2x^2+3x-2 = 0 \end{align}$$The polynomial \( \text{P}(x) = x^3-2x^2+3x-2 \) has three roots, one real (at \(x=1\) ) and two complex. See Figure 1.

Figure 1

The roots are:

• \( x_1=1 \)
• \( x_2 = \dfrac{1}{2}(1-i \sqrt{7}) \)
• \( x_3 = \dfrac{1}{2}(1+i \sqrt{7}) \)

These roots can be used to find any term in the sequence because of the following relationship:$$a_n=A(x_1)^n+B(x_2)^n+C(x_3)^n \text{ with A, B and C constants}$$Substituting the initial conditions we get three equations in three unknowns:$$ \begin{align} A + B + C &= 1 \\ Ax_1+Bx_2+Cx_3 &=1 \\ A(x_1)^2+B(x_2)^2+C(x_3)^2 &=0 \end{align} $$In terms of the roots, the values for \( A, B \text{ and } C \) are:$$ \begin{align} A = \frac{x_1 - x_2 x_3 - (x_2 + x_3)}{(x_1 - x_2)(x_1 - x_3)} \\ B = \frac{x_2 - x_1 x_3 - (x_1 + x_3)}{(x_2 - x_1)(x_2 - x_3)} \\ C = \frac{x_3 - x_1 x_2 - (x_1 + x_2)}{(x_3 - x_1)(x_3 - x_2)} \end{align} $$We know that when \(n=32\), the term is 28072 (my diurnal age) so let's check if that works by substituting the values of \( x_1,x_2 \text{ and } x_3 \) into and summarising at the same time what we've found previously:$$
\begin{array}{l}
\textbf{Step 1: Determine the Roots of the Characteristic Equation} \\[6pt]
x^3 - 2x^2 + 3x - 2 = 0 \\[4pt]
(x-1)(x^2 - x + 2) = 0 \\[4pt]
\text{The roots are:} \\[4pt]
x_1 = 1 \\[4pt]
x_2 = \dfrac{1 + i\sqrt{7}}{2} \\[4pt]
x_3 = \dfrac{1 - i\sqrt{7}}{2} \\[18pt]


\textbf{Step 2: Find Constants A, B, and C} \\[6pt]
\text{Using the initial conditions } a_0=1, a_1=1, a_2=0: \\[6pt]
A = \dfrac{1}{2} \\[6pt]
B = \dfrac{1}{4} - \dfrac{i}{4\sqrt{7}} \\[6pt]
C = \dfrac{1}{4} + \dfrac{i}{4\sqrt{7}} \\[18pt]


\textbf{Step 3: Construct the Explicit Formula} \\[6pt]
a_n = A(x_1)^n + B(x_2)^n + C(x_3)^n \\[6pt]
a_n = \dfrac{1}{2}(1)^n + \left(\dfrac{1}{4} - \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 + i\sqrt{7}}{2}\right)^n + \left(\dfrac{1}{4} + \dfrac{i}{4\sqrt{7}}\right)\left(\dfrac{1 - i\sqrt{7}}{2}\right)^n \\[18pt]


\textbf{Step 4: Verify for } n=32 \text{ (Detailed Breakdown)} \\[12pt] \text{We need to sum three terms: } \\[4pt] a_{32} = \underbrace{A(x_1)^{32}}_{\text{Term 1}} + \underbrace{B(x_2)^{32}}_{\text{Term 2}} + \underbrace{C(x_3)^{32}}_{\text{Term 3}} \\[18pt] \textbf{1. Calculate Term 1 (The Real Root)} \\[6pt] \text{Since } x_1 = 1 \text{ and } A = 0.5: \\[6pt] \text{Term 1} = 0.5 \cdot (1)^{32} = \mathbf{0.5} \\[18pt] \textbf{2. Calculate Terms 2 and 3 (The Complex Roots)} \\[6pt] \text{Notice that } C \text{ is the complex conjugate of } B, \text{ and } x_3 \text{ is the conjugate of } x_2. \\[6pt] \text{This implies that Term 3 is the complex conjugate of Term 2.} \\[6pt] \text{Mathematical Rule: } Z + \bar{Z} = 2 \cdot \text{RealPart}(Z). \\[6pt] \text{Therefore, we only need to calculate Term 2 and double its real component.} \\[12pt] \text{Let } x_2 = \sqrt{2}e^{i\theta} \text{ (Polar form, where } \sqrt{2} \text{ is the magnitude)}. \\[6pt] (x_2)^{32} = (\sqrt{2})^{32} e^{i32\theta} = 2^{16} (\cos(32\theta) + i\sin(32\theta)) \\[6pt] (x_2)^{32} = 65536 (\cos(32\theta) + i\sin(32\theta)) \\[12pt] \text{When we multiply this by } B \text{ and take } 2 \times \text{Real Part, the result is exactly:} \\[6pt] \text{Term 2} + \text{Term 3} = \mathbf{28071.5} \\[18pt] \textbf{3. Final Total} \\[6pt] a_{32} = \text{Term 1} + (\text{Terms 2 \& 3}) \\[6pt] a_{32} = 0.5 + 28071.5 \\[6pt] a_{32} = \mathbf{28072} \end{array} $$

Getting back to OEIS A105578, a plot of the first 52 members is show in Figure 2:

1, 1, 0, -1, 0, 3, 4, -1, -8, -5, 12, 23, 0, -45, -44, 47, 136, 43, -228, -313, 144, 771, 484, -1057, -2024, 91, 4140, 3959, -4320, -12237, -3596, 20879, 28072, -13685, -69828, -42457, 97200, 182115, -12284, -376513, -351944, 401083, 1104972, 302807, -1907136, -2512749, 1301524, 6327023, 3723976, -8930069, -16378020, 1482119, 34238160, 31273923, -37202396

Figure 2: permalink

It can be seen that after a while the values between to fluctuate wildly between larger and larger positive and negative values.

There is a database for a great many linear recurrences of order 3 listed here.

Fibonacci-like Sequences

Consider the following recurrence relation:$$ \text{a} (n)=\text{a} (n-1)+\text{a} (n-8)\\ \text{with } \text{a}(i)=1 \text{ for } i=0 \dots 7 $$The ratio of successive terms approach the golden ratio \( \phi \) just as the terms in the Fibonacci sequence do. Naturally, the terms in the sequence take a while to grow larger. Here are the initial terms:

1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 14, 18, 23, 29, 36, 44, 53, 64, 78, 96, 119, 148, 184, 228, 281, 345, 423, 519, 638, 786, 970, 1198, 1479, 1824, 2247, 2766, 3404, 4190, 5160, 6358, 7837, 9661, 11908, 14674, 18078, 22268, 27428, 33786, 41623

These terms form OEIS A005710. The generating function (permalink) for this sequence is:$$ \frac{1}{1-x-x^8}$$In general, we have:$$a(n) = a(n-1) + a(n-m) \\ \text{ with } a(n) = 1 \text{ for } n = 0 \dots m-1$$The generating function is:$$ \frac{1}{1-x-x^m}$$In the case of \(m=2\), we get the terms in the Fibonacci sequence.

Somos Sequences

I came across an interesting article in Quanta Magazine, dated November 16th 2023, that mentions Somos sequences that I'd not heard of before. To quote from the article:

A Somos-\(k\) sequence starts with the digit or digits 1, \(k\) of them. Each new term of a Somos-\(k\) sequence is defined by pairing off previous terms, multiplying each pair together, adding up the pairs, and then dividing by the term \(k\) positions back in the sequence.

The sequences aren’t very interesting if \(k\) equals 1, 2 or 3 — they are just a series of repeating ones. But for \(k\) = 4, 5, 6 or 7 the sequences have a weird property. Even though there is a lot of division involved, fractions don’t appear.

Figure 1 shows an excerpt from the article that illustrates how the Somos-5 series is generated.

Figure 1

It's easy enough to write some SageMath code to generate the Somos-5 and here are the initial terms and, as can be seen, the terms get very large very quickly.

1, 1, 1, 1, 1, 2, 3, 5, 11, 37, 83, 274, 1217, 6161, 22833, 165713, 1249441, 9434290, 68570323, 1013908933, 11548470571, 142844426789, 2279343327171, 57760865728994, 979023970244321

These terms constitute OEIS A006721  (permalink): 

A006721

Somos-5 sequence: a(n) = (a(n-1) * a(n-4) + a(n-2) * a(n-3)) / a(n-5), with a(0) = a(1) = a(2) = a(3) = a(4) = 1.

The Somos-4 sequence is OEIS A006720 (permalink):

A006720

Somos-4 sequence: a(0)=a(1)=a(2)=a(3)=1; for n >= 4, a(n) = (a(n-1) * a(n-3) + a(n-2)^2) / a(n-4).

The initial members are:

1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898, 126742987, 1687054711, 47301104551, 1123424582771, 32606721084786, 1662315215971057, 61958046554226593, 4257998884448335457, 334806306946199122193

The Somos-6 series is OEIS A006722:

A006722

Somos-6 sequence: a(n) = (a(n-1) * a(n-5) + a(n-2) * a(n-4) + a(n-3)^2) / a(n-6), a(0) = ... = a(5) = 1.

The initial members are:

1, 1, 1, 1, 1, 1, 3, 5, 9, 23, 75, 421, 1103, 5047, 41783, 281527, 2534423, 14161887, 232663909, 3988834875, 45788778247, 805144998681, 14980361322965, 620933643034787, 16379818848380849, 369622905371172929, 20278641689337631649, 995586066665500470689

The Somos-7 series is OEIS A006723:

A006723

Somos-7 sequence: a(n) = (a(n-1) * a(n-6) + a(n-2) * a(n-5) + a(n-3) * a(n-4)) / a(n-7), a(0) = ... = a(6) = 1.

The initial members are:

1, 1, 1, 1, 1, 1, 1, 3, 5, 9, 17, 41, 137, 769, 1925, 7203, 34081, 227321, 1737001, 14736001, 63232441, 702617001, 8873580481, 122337693603, 1705473647525, 22511386506929, 251582370867257, 9254211194697641, 215321535159114017

Pisot Sequences

Thanks to the number associated with my diurnal age today, 27204, I was introduced to so-called Pisot sequences that I'm still coming to terms with. Let's start with one of the properties of this number, namely its membership in OEIS A048589:

A048589

Pisot sequence L(7, 9).

The members of the sequence are derived using the following formula:

$$a(n)= \Biggl \lceil \frac{a(n - 1)^2}{a(n - 2)} \Biggr \rceil \\ \text{ where } n \geq 2 \text{ with }a(0)=7 \text{ and } a(1)=9$$The initial members of the sequence are:

7, 9, 12, 16, 22, 31, 44, 63, 91, 132, 192, 280, 409, 598, 875, 1281, 1876, 2748, 4026, 5899, 8644, 12667, 18563, 27204, 39868, 58428, 85629, 125494, 183919, 269545, 395036, 578952, 848494, 1243527, 1822476, 2670967, 3914491, 5736964, 8407928, 12322416, 18059377

However, exactly the same sequence of numbers can be derived from the recurrence relation:$$a(n)=2a(n-1)-  a(n-2) + a(n-3) - a(n-4)\\ \text{ with } a(0)=7, a(1)=9, a(2)=12 \text{ and } a(3)=16$$However, the equivalence may last only up to \(n=1000\) according to the OEIS comments. After that, there is uncertainty. Permalink.

Let's take another example using OEIS A018910:

A018910

Pisot sequence L(4, 5).

Once again, the previous formula can be used with different starting values:$$a(n)= \Biggl \lceil \frac{a(n - 1)^2}{a(n - 2)} \Biggr \rceil \\ \text{ where } n \geq 2 \text{ with }a(0)=4 \text{ and } a(1)=5 $$The initial members of the sequence are:

4, 5, 7, 10, 15, 23, 36, 57, 91, 146, 235, 379, 612, 989, 1599, 2586, 4183, 6767, 10948, 17713, 28659, 46370, 75027, 121395, 196420, 317813, 514231, 832042, 1346271, 2178311, 3524580, 5702889, 9227467, 14930354, 24157819, 39088171, 63245988, 102334157, 165580143

Again, the same sequence can be generated using the recurrence relation (permalink):$$a(n)=2a(n-1)- a(n-3)\\ \text{ with } a(0)=4, a(1)=5 \text{ and } a(2)=7 $$Just to confuse matters we can also generate the sequence using:$$a(n) = \text{ Fibonacci}(n+3)+2$$What the letter L signifies I don't know. Other letters are used with Pisot sequences, including E, P and T. Not all Pisot sequences use the ceiling function. Some use the floor function and others add or subtract a constant. There's not a great deal of introductory information out there about these sorts of sequences. You find yourself in deep mathematical matters very quickly once you start to explore the topic. 

Here is what Google's Bard had to say about them:

Pisot sequences are a type of infinite sequence of real numbers that have a number of interesting and useful properties. They are named after the French mathematician Charles Pisot, who first studied them in the 1930s.

Simple examples of Pisot sequences include:

• The Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
• The Lucas sequence: 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...
• The Parry sequence: 0.1101001000101101...

Pisot sequences are important because they have a number of unique properties. For example:

• They are all irrational numbers.
• They are all aperiodic (meaning that they never repeat themselves exactly).
• They are all dense in the real numbers (meaning that between any two real numbers, there is always a Pisot number).

Pisot sequences are connected to Pisot numbers and Salem numbers in the following way:

• A Pisot number is a real number that is greater than 1 and has the property that all of its conjugates are less than 1.
• A Salem number is a real number that is greater than 1 and has the property that all of its conjugates are either less than 1 or equal to 1.

Every Pisot number is the limit of a Pisot sequence, and every Pisot sequence converges to a Pisot number. Salem numbers are a special type of Pisot number.

Here are some of the applications of Pisot sequences:

• They can be used to generate random numbers.
• They can be used to model complex systems, such as the growth of populations and the spread of diseases.
• They can be used to design efficient algorithms for tasks such as sorting and searching.
• Pisot sequences are a fascinating and important area of mathematics, and they have a wide range of applications in other fields.

More on Linear Recurrence

This post is a follow on from an earlier post, titled Solving Linear Recurrence Relations of June 16th 2020, in which I dealt only with polynomials having real roots. Here I look at an example of a polynomial with one real root and two complex roots.

Suppose we have the following recurrence:$$a_n=a_{n-1}-a_{n-2}+a_{n-3} \text{ with } a_0=1, a_2=2, a_3=3$$This corresponds to \(x^3=x^2-x+1\) and thus we can write:

$$ \begin{align}
P(x)&=x^3-x^2+x-1\\
&=x^2 \,(x-1)+1 \, (x-1)\\
&=(x^2+1)(x-1)
\end{align}$$with solutions of \(x=1, \pm \, i\) when \(P(x)=0\). The \(n\)-th term can be written as a linear combination of these three solutions and thus:$$a_n=A \cdot (1)^n+B \cdot i^n+C \cdot (-i)^n \text{ with } A, B, C \text{ constants }$$We apply the initial conditions then to find the values of \(A, B, C\) by creating three equations in the three unknowns:$$\begin{align}
A+B+C&=1 \text{ when }n=0\\
A+B\,i-C \,i&=2 \text{ when }n=1\\
A-B-C&=3 \text{ when }n=2
\end{align}$$Solving these we find that:$$\begin{align}
A&=\frac{2}{5}\\
B&=-\frac{i+2}{10}\\
C&=\frac{i-2}{10}
\end{align}$$This means that \(a_n\) is then given by:$$a_n=\frac{2^{n+2}-i^{\,n}\,((i+2)-(i-2) \,(-1)^n)}{10}$$This satisfies the original conditions and will generate all terms: 0, 1, 2, 3, 6, 13, 26, 51, 102, 205, 410, 819, 1638, 3277, 6554, 13107, 26214, 52429, 104858, 209715, 419430, 838861, 1677722, ...

Even though the formula contains \(i\)'s, they always cancel out to produce real numbers. My interest in this topic was rekindled when I looked at my diurnal age (26200) and found that it could be generated by the following linear homogenous recurrence:$$a(n)=a(n-1)+a(n-3) \text{ with } a(0)=3, a(1)=1, a(2)=4 \text{ and } n≥3$$This lead to a polynomial with one real root and two complex roots, namely:$$P(x) = x^3 - x^2 - 0 \cdot x - 1 = x^3 - x^2 - 1$$However, the roots are nasty and so I chose to deal with a simpler but similar polynomial in this post. 

To see how the terms of the first sequence$$a_n=a_{n-1}-a_{n-2}+a_{n-3}$$ can be generated from the initial values$$a_0=1, a_2=2, a_3=3$$or from the formula for the \(n\)-th term$$a_n=\frac{2^{n+2}-i^{\,n}\,((i+2)-(i-2) \,(-1)^n)}{10}$$follow this SageMathCell permalink. Clearly, we also have:$$ \lim_{n \to \infty} \frac{a_{n+1}}{a_n}=2$$

Lucas' Problem of the Married Couples

I've seen this problem before but I thought it interesting to revisit it and look at its historical background. This is Problem 8 in "100 Great Problems of Elementary Mathematics" by Heinrich Dörrie. The problem is stated as follows:

How many ways can \(n\) married couples be seated about a round table in such a manner that there is always one man between two women and none of the men is ever next to his own wife?

This problem appeared (probably for the first time) in 1891 in the Theorie des Nombres of the French mathematician Edouard Lucas (1842-1891), author of the famous work Récréations mathématiques. The English mathematician Rouse Ball has said of this problem, “The solution is far from easy.” The problem has been solved by the Frenchmen M. Laisant and M. C. Moreau and by the Englishman H. M. Taylor. A solution based upon modern viewpoints is to be found in MacMahon’s Combinatory Analysis. The approach adopted here is essentially that of Taylor (The Messenger of Mathematics, 32, 1903).

I spent quite some time, on and off, attempting my own solution before coming up short. It was a useful exercise however, because I explored various approaches and the most promising to me seemed to be one involving Cartesian products, so I got a fair bit of practice in working with these products. Once again I was trying for a brute force approach using SageMathCell to create all possible permutations and then imposing progressive restrictions on these permutations. However, the number of permutations quickly become huge and SageMathCell timed out for \(n=5\) and beyond.

According to WolframMathWorld, a closed form expression for \(n>1\) in terms of a sum due to Touchard (1953) is:$$A_n=\sum_k ^n \frac{2n}{2n-k} \binom{2n-k}{k} (n-k)! \, (-1)^k$$Once the formula is known it's easy enough to execute in SageMathCell. Here is the permalink to the calculation up to \(n=10\). The reason I'm quoting from WolframMathWorld and not the original book is that the explanation runs for several pages. Quite simply, as Rouse Ball put it, "the solution is far from easy". Wikipedia gives a simple, four-term recurrence (here is a permalink to the SageMathCell execution of it): $$ A_n = n \, A_{n-1}+2 \, A_{n-2}-(n-4) \, A_{n-3} - A_{n-4} $$ $$ \text{ with } A_2=0, A_3=1,A_4=2,A_5=13$$Wikipedia refers to this sequence of numbers as the mènage numbers and they form OEIS A000179, shown here for \(n=2 \text{ to } 10\):$$0, 1, 2, 13, 80, 579, 4738, 43387, 439792, ... $$It's clear that the number of arrangements increases at a very rapid rate. For just ten couples, there are almost half a million possibilities. The problem has connections with graph theory, knot theory and even chess (see Rooks Problem) but overall I found the problem rather too daunting and didn't have the patience or motivation to wade through the explanation in the book.

However, I'll quote the basis of the book's explanation:

The wives will then all have to be seated on the even- or odd-numbered chairs. In each of these two cases there are \(n!\) dif­ferent possible seating arrangements, so that there are \(2n!\) different possible seating arrangements for the women alone. We will assume that the women have been seated in one of these arrangements and we will maintain this seating arrangement through­ out the following. The nucleus of the problem then consists of deter­mining the number of possible ways of seating the men between the women.

Let us designate the women in the assumed seating sequence as \(F_1, F_2, ..., F_n \), their respective husbands \(M_1, M_2, ...,M_n\), the couples \( (F_1, M_1), (F_2,M_2),...,\) as \(1,2,...\) and the arrangements in which there are \(n\) married couples as \(n\)-pair arrangements. Let us designate the husbands about whom we have no further information as \(X_1, X_2, ...\).

Let \(F_1X_1F_2X_2,...,F_nX_n,F_{n+1}X_{n+1} \) be an (\(n+1)\)-pair arrangement in which none of the husbands sits beside his own wife. It must be remembered that the arrangement is circular, so that \(X_{n+1}\) is seated between \(F_{n+1}\) and \(F_1\). If we take \(F_{n+1}\) and \(M_{n+1}=X_{\nu}\) out of the arrangement and replace \(X_{\nu} \) with \(X_{n+1}=M_{\mu}\), we obtain the \(n\)-pair arrangement: $$F_1X_1F_2X_2...F_{\nu}M_{\mu}F_{\nu+1}...F_nX_n $$This arrangement can occur in three ways:

1. No man sits next to his wife (thus \( M_{\mu} \neq M_{\nu},M_{\mu} \neq M_{\nu+1}, X_n \neq M_1\)).

1. One man sits next to his own wife (namely when \(M_{\mu}=M_{\nu}\) or \(M_{\mu}=M_{\nu+1}\) or else \(X_n=M_1\)).

1. Two men sit next to their own wives (when \(M_{\mu}=M_{\nu}\) or \(M_{\mu}=M_{\nu+1}\) and at the same time \(X_n=M_1\), that is, when in our arrangement the order \(M_1F_1\) occurs.

It goes on and on from there but that's the start of the explanation anyway. On looking further ahead in the book, it seems that in general the problems are rather too difficult for a recreational mathematician to approach. For that reason, I may go back to Project Euler of which I've solved only 8 out of the 723 available problems. These problems are mathematical and require a programming solution.

Prouhet-Thue-Morse Sequence

I was reminded of this sequence when I rewatched a Numberphile YouTube video that related the sequence to the game of chess.

The Prouhet-Thue-Morse is a simple enough sequence but one with many practical applications. It can be described using formal mathematical notation but it can be described in so-called layman's terms as well. This gif from Wikipedia is an example of the latter:

A close look at this gif and it's clear enough how the sequence is being constructed. My last two posts have focussed on recurrence relations and the Prouhet-Thue-Morse sequence can be described more formally as a recurrence relation:$$ \begin{align} t_0 &= 0\\ t_{2n} &= t_n\\ t_{2n+1} &= 1 - t_n \end{align}$$wikiHow has a variety of algorithms for creating the sequence. One uses the recurrence relation as shown in Figure 1:

Figure 1

I incorporated this approach into SageMathCell as shown in Figure 2 (permalink):

Figure 2: permalink

Another approach, what wikiHow calls the Direct Definition, uses the binary form of the natural (decimal) numbers, calculates their binary sum and then uses the modulus 2 of this sum as the output. What's happening is that decimal numbers with an even number of 1's in their binary form are assigned a ZERO and those with an odd number of 1's are assigned a ONE.

\(t_0 = 0 \text{ and } t_n \equiv s_n \bmod{2} \text{ where }s_n \text{ is the binary sum of }n\)

This algorithm is even easier to implement in SageMathCell. See Figure 3 where the output is shown, for variety, as a string rather than a list of elements (permalink):

Figure 2: permalink

The following is an excellent video that I came across from a mathematician who, unconsciously, used the Thue-Morse sequence (sometimes the Prouhet part of the name is omitted) as a child to cope with his obsessive compulsive disorder. Later he describes how he unwittingly used the sequence to solve the Mathematics problem described in Figure 3:

Figure 3

Of course the sequence can be represented with elements other than 0's and 1's. For example, suppose that two persons want to divide an even number of items of equal value between themselves. If the choosing sequence goes ABABABAB ... or BABABABA ... then the person choosing second will always be behind 50% of the time in terms of what they've accumulated. However, using the Thus-Morse sequence, the lead will alternate and in fact represents the fairest way to share things:

ABBABAABBAABABBABAABABBAABBABAABBAABABBAABBABAABABB

Finally, here is a video on the sequence that Stand-up Maths did some years ago:

Solving Linear Recurrences

This article follows on from my previous post of June 10th 2020 titled Fibonacci-like Sequences. I owe a debt of gratitude to Niloufar Shafiei who has posted an excellent PDF about solving linear recurrence relations. He treats both linear homogeneous recurrences and linear non-homogeneous recurrences but it is only the former that I'll concern myself with in this post.

With a linear recurrence, each term of a sequence is a linear function of earlier

terms in the sequence. An example would be:$$a_n=a_{n-1}+a_{n-2}+1$$However, this is not homogenous, because the last term, 1, does not involve an earlier term of the sequence. An example of a linear homogenous recurrence would be:$$a_n=a_{n-1}+2a_{n-2} \text{ with }a_0=1 \text{ and }a_1=5$$This corresponds to the quadratic:$$x^2=x+2 \text{ so that }x^2-x-2 = (x-2)(x+1)$$This equals 0 when \(x=2\) or \(x=-1\).

The PDF referred to earlier shows that the \(n\)-th term can be written in a form that is a linear combination of the two solutions:$$ \alpha_1(2^n)+\alpha_2(-1)^n \text{ where } \alpha_1 \text{ and } \alpha_2 \text{ are constants to be determined}$$The values of \(\alpha_1 \text{ and } \alpha_2 \) can be determined from the initial conditions. When we substitute for \(n=0\) and \(n=1\), this means that:$$\alpha_1+\alpha_2=1 \text{ and } 2 \alpha_1-\alpha_2=5$$Solving this pair of equations, we find \( \alpha_1=2\) and \( \alpha_2=-1\) and thus \(a_n\) can be written as:$$a_n=2^{n+1}-(-1)^n \text{ for } n \ge 0$$The dominant term of course is \(2^n\) and so:$$\lim_{n -> \infty}\frac{a_{n+1}}{a_n}=2$$The first ten terms of this sequence are (SageMathCell permalink):

1, 5, 7, 17, 31, 65, 127, 257, 511, 1025, 2047, 4097

If the quadratic associated with the recurrence relation has a repeated root, then a slightly different approach is required. For example, let's consider the recurrence:$$a_n=6a_{n-1}-9a_{n-2} \text{ with } a_0=1 \text{ and } a_1=9$$The quadratic that arises is:$$x^2=6x-9 \text{ or } x^2-6x+9=(x-3)^2$$The repeated root here is \(x=3\) and Niloufar Shafiei in his PDF shows that in this case, the solution is:$$\alpha_1(3)^n+\alpha_2 n(3)^n \text{ or } 3^n(\alpha_1+\alpha_2n)$$Again, we get two equation in two unknowns and in this case, after applying the initial conditions, the solution is \(\alpha_1=1\) and \(\alpha_2=2\). Thus \(a_n\) can be written as:$$a_n=3^n(1+2n) \text{ for } n \ge 0$$The dominant term is \(3^n\) and so:$$\lim_{n -> \infty}\frac{a_{n+1}}{a_n}=3$$The first ten elements of the sequence are (SageMathCell permalink):

1, 9, 45, 189, 729, 2673, 9477, 32805, 111537, 373977, 1240029, 4074381

So this is the essential idea. Niloufar Shafiei in his PDF has plenty more examples that are easy to understand and well-presented. There is a lot more to delve into regarding recurrence equations and I'm sure I'll be writing more about them in the future.

Fibonacci-like Sequences

I've posted a lot about Fibonacci numbers over the years:

• The Fibonacci Number Base
• Finance and Fibonacci
• Random Fibonacci Numbers
• Finding Fibonacci and Tribonacci Seed Numbers
• Beyond Fibonacci
• Vishwanath Number
• Metallic Means

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:$$ a_n=\begin{cases}a&\mbox{if }n=0;\\b&\mbox{if }n=1;\\a_{n-1}+a_{n-2}&\mbox{otherwise.}\end{cases} $$No matter what the values of the seed numbers, the ratio of one term to its predecessor always approaches \( \phi \), the golden ration. This ratio is equal to: $$ \frac{1+\sqrt{5}}{2}$$There is an even more generalised sequence that also begins with two seed numbers \( a \) and \( b \) but then proceeds as follows:$$ a_n=\begin{cases}a&\mbox{if }n=0;\\b&\mbox{if }n=1;\\A \, a_{n-1}+ B \, a_{n-2}&\mbox{otherwise.}\end{cases} $$Here \(A\) and \(B\) are constants and in the case where \(A=1\) and \(B=1\), we have the earlier sequence. The ratio of one term to its predecessor however, is no longer the golden ratio. The \(n\)-th term for such a sequence is given by:$$\frac{ \alpha^n- \beta^n}{\alpha-\beta}$$Here \( \alpha \) and \( \beta \) are the roots of the quadratic \(x^2=Ax+B\). Let's take a specific example where \(A=3\) and \(B=3\) and so \(x^2=3x+3\). The solution to this is:$$\alpha=\frac{3+\sqrt{21}}{2} \text{ and } \beta=\frac{3-\sqrt{21}}{2}$$Thus the \(n\)-th term approaches:$$\frac{(3+\sqrt{21})^n- (3-\sqrt{21})^n}{2^n \times \sqrt{21}}$$This simplifies to:$$\frac{1}{\sqrt{21}}\, \left(\frac{3+\sqrt{21}}{2}\right)^n$$Thus the ratio between successive terms will tend to \( \displaystyle \frac{3+\sqrt{21}}{2}\)

In the case where \(A=1\) and \(B=1\), the ratio is  \( \displaystyle \frac{1+\sqrt{5}}{2}=\phi\) and so different surds will appear depending on the values of \(A\) and \(B\).

As we've seen in the case of \(A=3\) and \(B=3\), the surd turns out to be \( \sqrt{21} \). Here is an example of an OEIS sequence with seed numbers \(a_0=1\) and \(a_1=2\) that has both constants equal to 3:

A202206

a(n) = 3*a(n-1) + 3*a(n-2) with a(0)=1 and a(1)=2

The first terms of the sequence are 1, 2, 9, 33, 126, 477, 1809, 6858, 26001, 98577, 373734, 1416933, ... Naturally the terms get larger far more quickly than the Fibonacci sequence. Note that the ratio of the last two terms is getting close to the predicted value:$$\frac{1416933}{373734} \approx 3.79128738621586 \text{ and } \frac{3+\sqrt{21}}{2} \approx 3.79128784747792$$A further point to note is that the formula: $$\frac{ \alpha^n- \beta^n}{\alpha-\beta}$$only produces the correct terms of the sequence when a(0)=0 and a(1)=1 and the result is rounded to the nearest whole number. See permalink. However, no matter what the seed numbers, the ratio of terms for a particular sequence always approaches the same limit.