### Catalan pseudoprimes

As a special case of Fermat’s little theorem, if is an odd prime number then is divisible by , or, in the language of congruences, .

The converse of this is not true: if where is a positive integer, it does not follow that is prime. For example could be . There are infinitely many such .

Composite integers that pass a test for prime numbers are commonly known as *pseudoprimes*. Of course whether a composite number is regarded as a pseuodprime depends on the particular prime number property we are using.

Another property of primes involves the Catalan numbers. These are the numbers defined by the recurrence relation and .

The Catalan numbers can also be defined recursively by .

The Catalan numbers are the coefficients of in the series expansion of

The Catalan numbers up to 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.

Clearly grows rapidly with . In fact in the sense that the ratio of to approaches 1 as :

Theorem 2 of Aebi & Cairns (see below) provides a property of prime numbers in terms of Catalan numbers:

If is an odd prime, then

On the other hand, there are numbers other than primes that also have this property, for example .

Aebi & Cairns call a composite number a *Catalan pseudoprime* if . Thus, 5907 is a Catalan pseudoprime.

Currently the only known Catalan pseudoprimes are:

The object of this project is to use computational methods to find other Catalan pseudoprimes in order to help determine how frequently they occur.

The following two lines of **Mathematica**® code:

**n = 1;
While[Or[Mod[(-1)^((n - 1)/2)*CatalanNumber[(n - 1)/2], n] != 2, PrimeQ[n] == True], n = n + 2]**

found 5907 in 1.86 seconds.

Beyond that things are much more difficult.

### A related question

The Catalan numbers are related to the middle binomial coefficients . When is odd, say , we have . A theorem of Erdös (see Finch, 2007, below) shows that almost always the middle binomial coefficient is divisible by high powers of small primes. Let denote the smallest odd prime dividing . How does vary with k? A plot of is shown below.

This plot indicates that although commonly, there are values of k for which becomes much larger. In light of the theorem of Erdös cited above, a fundamental question is whether the numbers stay bounded as k increases.

The plot below shows the running average of the values of . It indicates that, possibly, .

**Behavior of a number-theoretic function**

The function takes the value 1 exactly when is prime or a Catalan pseudoprime. How does behave as a function of ?

A plot of , below, indicates that is bounded above by a linear function of but has wide variation:

A plot for shows similar behavior, but appears more dense on the same scale:

This is more or less what we would expect if the values of distributed themselves relatively uniformly across the remainders . A plot of the running average , and of the running standard deviation , indicates a linear increase with :

How does the function behave as a function of ? The plot below indicates that the values are not uniformly distributed:

A blow-up around the value shows the following behavior:

Similar behavior holds around the value .

Similar, but weaker, behavior occurs around the values :

### References & readings

- Christian Aebi & Grant Cairns. Catalan numbers, primes and twin primes. (cairns_catalan)
- Campbell, D. The Computation of Catalan Numbers. Math. Mag. 57, 195-208, 1984
- Steven Finch (March 28, 2007)Central Binomial Coefficients (central_binomial_coefficients_finch)
- Tom Davis (2006) Catalan Numbers (catalan_numbers1)
- David Fowler, The Binomial Coefficient Function. The American Mathematical Monthly, Vol. 103, No. 1 (Jan., 1996), pp. 1-17.
- W. Sander, A Story of Binomial Coefficients and Primes, The American Mathematical Monthly, Vol. 102, No. 9 (Nov., 1995), pp. 802-807
- Keith Ball (2006). Strange Curves, Counting Rabbits, & Other Mathematical Explorations. Princeton University Press. ISBN-13: 978-0691127972

## 1 comment

Comments feed for this article

April 9, 2013 at 11:59 pm

Bernard CasavantThe last catalan factorization should be 3511 x 3511 instead 3511 x 351