Catalan Numbers

Today I turned \(24285\) days old and Figure 1 shows my Twitter post to commemorate the occasion:

Figure 1

The sequence referred to in the tweet is OEIS A178854 and its members, up to and including \(384733\), can be generated using the SageMath code shown in Figure 2.

Figure 2: permalink

The resultant output is: 1, 1, 5, 13, 29, 29, 93, 221, 221, 733, 1757, 3805, 7901, 7901, 24285, 57053, 122589, 122589, 384733, 384733.

Of course, it got me thinking about what a Catalan number is (let alone an odd Catalan number). It turns out that "the only Catalan numbers \(C_n\) that are odd are those for which \(n = 2^k − 1\). All others are even" (Wikipedia). But firstly, what are the Catalan numbers? Here is a definition from the same Wikipedia source where zero-based numbering is used and the \(n\)-th Catalan number is given by:$$C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} = \prod\limits_{k=2}^{n}\frac{n+k}{k} \qquad\text{for }n\ge 0$$The first Catalan numbers for n = 0, 1, 2, 3, ... are:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, ... (sequence A000108 in the OEIS)

Note that when \(n =2^2-1=3, n = 2^3-1=7, n=2^4-1=15\) etc., the corresponding Catalan numbers are odd (\(5, 429, 9694845\)). The odd Catalan numbers form the OEIS A038003. Of interest here of course is the 15th Catalan number \(9694845\) and the fact that \(9694845 \! \! \mod 2^{15}= 24285\). 

An example of the practical applications of Catalan numbers is shown in Figure 3 (again taken from the Wikipedia article) illustrating their application to Dyck paths:

Figure 3

Of course there's a lot more to Catalan numbers than this and reading the Wikipedia article thoroughly as well the WolframAlpha entry is a start to understanding these numbers more deeply.

on December 19th 2020

There is a later post on April 15th 2018 titled
Sums of Squares of Integers and Catalan Numbers

Sum of Two Squares

Figure 1

I'm currently reading the book whose cover appears in Figure 1. As the title suggests, the author just deals with the numbers from \(1\) to \(9\). While some of the topics are a little inaccessible, the majority are understandable and several of them I'll be revisiting in subsequent posts.

I'll address one of the topics here and now however, and this one concerns the conditions necessary for a prime number to be expressed as a sum of two squares. Fermat's theorem on the sums of two squares states that any prime number that is congruent to 1 modulus 4 can be expressed as a sum of two squares. Another way of expressing this is to say that the prime can be represented as \(4k+1\) for some \(k \geq 1\). 

The first instance of such a prime is 5, corresponding to \(k=1\), and it can be expressed as \(2^2+1^2 \). When \(k=3\), we have the prime 13 and it can be expressed as \(3^2+2^2\). My last prime day is another example and is expressible as: \(24281= 16^2+155^2\). 

However, what if the number is composite? It appears that the condition in that case is that none of the \(4k+3\) primes can have an odd exponent. For example, \(21=3 \times 7 \) with both 3 and 7 being of the form \(4k+3\) with \(k=0\) and \(k=1\) respectively. Both are raised to the odd power 1 and thus 21 cannot be written as a sum of two squares.

However, \(45=3^2 \times 5 \) and, though 3 is a factor, it is raised to an even power. Thus 45 can be written as a sum of two squares, specifically \(6^2+3^2\). A larger composite number is \(24274=2 \times 53 \times 229\) and it is expressible as a sum of two squares in two ways, namely \(24274=57^2+145^2\) and \(93^2+125^2\). In this case, none of the prime factors is of the \(4k+3\) variety.

To determine in how many ways a number can be written as a sum of two squares, all that needs to be done is to:

• add 1 to the index of each 4\(k\)+1 factor
• multiply these new indices together
• divide the product by 2
• if the product is an odd number, then round up

If 2 or a power of 2 is present, it has no effect and, as we said, all \(4k+3\) factors must be raised to even powers. In the case of 24274, the indices of 53 and 229 are 1 and 1 respectively which become 2 and 2. Multiplying 2 by 2 and dividing by 2 gives 2 and thus its representation as a sum of two squares in two different ways.

In the case of a number that is a perfect square \(n\), the trivial \(0^2+(\sqrt(n))^2\) is also included as a solution. For example, consider 25 = 5 * 5. The rule again gives 2 by 2 divided by 2 and so there are two ways to express the number as a sum of two squares. One way is \(3^2+4^2\) and the other way is \(0^2+5^2\).

As a further example, consider the perfect square:$$ \begin {align} 710222500 &=26650^2\\ &=2^2 \times 5^4 \times 13^2 \times 41^2 \end{align}$$This number has \(4k+1\) indices of 4, 2, 2 which become 5, 3, 3 when 1 is added. The product is 45 which, when divided by 2 and rounded up, becomes 23. So there are 22 ways in which the number can be expressed a sum of two positive integers and the other way is as \(0^2+26650^2\).

on December 19th 2020, December 22nd 2021 and March 21st 2022

This future post in May 2018 collects a variety of posts (including this one) 

that relate to the topic of the sums of squares.

Prime Gaps

Figure 1: permalink

As I keep my tally of the days that have passed since my birth, I've noticed that lately the primes have become a little thin. To be specific, on August 26th 2015 I celebrated prime day 24251. It was to be prime day 24281 (yesterday) before the drought of primes would be broken, a gap of 30 days. The next prime day is now 24317, a gap of 36. 

The bottom half of Figure 1 shows where the maximum gaps occur for the smallest prime numbers. For example, after prime 9551 there is a gap of 36 (so the next prime is 9587) and that was the first time a gap of that magnitude occurred. 

Of course the average gap to the next prime for any prime p is given approximately by ln(p) and ln(24281)= 10.097 or just 10 for short. The gap increases slowly as the numbers become larger but even at 242810 for example, the log returns 12.400. Well, the prime days will flow again but now the next one is five weeks away. So it goes.

The top half of Figure 1 is the SageMath code used to make a dictionary that records the record gaps up to one hundred million (100,000,000) mark  and output the result in tabular form.

If we want to search for occurrences of specific gaps, Figure 2 shows the primes (up to 30,000) that are followed by gaps of 36. The first occurrence is 9551 and a later one is 24281 as mentioned earlier.

Figure 2: permalink

on December 18th 2020 

Canva link added 
on December 21st 2021

Presented by SEAN REEVES by Sean Reeves