# Number Theory

In previous posts we have established the asymptotic densities of the Motzkin numbers modulo $2^{k}, k \in \{1, 2, 3 \}$ and $5$. The main result of this note is that

Theorem 1.

$\lim_{N \to \infty} \frac {1}{N} \#\{n \leq N: M_n \equiv 0 \mod 3 \} = 1$.

Firstly, let $T(\, 01 )\,$ denote the set of natural numbers which have a base 3 expansion containing only the digits $0$ and $1$. The following theorem from [1] will be used to prove theorem 1.

Theorem 2. (Corollary 4.10 of [1]). The Motzkin numbers satisfy

$M_n \equiv -1 \mod 3 \quad$ if  $\quad n \in 3T (\, 01 )\, - 1$,

$M_{n} \equiv 1 \mod 3 \quad$  if  $\quad n \in 3T(\, 01 )\quad$ or $\quad n \in 3T(\, 01 )\, - 2$,

$M_n \equiv 0 \mod 3 \quad$ otherwise.

We will first examine the nature of the set $T(\, 01 \,)$. We have

Theorem 3. The asymptotic density of the set $T(\, 01 \,)$ is zero.

Proof:

Choose $k \in N: 3^{k} \leq N < 3^{k+1}$. Then $k = \lfloor log_3 (\, N )\, \rfloor$ and

$\frac {1}{N} \# \{ n \leq N : n \in T(01) \} \leq \frac {2^{k+1}}{N} \leq \frac {2^{k+1}}{3^{k}} \to 0$ as $N \to \infty$.

$\Box \,$ .

Proof of Theorem 1.

Since the asymptotic density of $T(\, 01 \,)$ is zero, so is the asymptotic density of the sets $3T(\, 01 \,) - k$ for $k \in \{0, 1, 2\}$. Therefore Theorem 2 implies that

$\lim_{N \to \infty} \frac {1}{N} \# \{n \leq N : M_n \equiv +-1 \mod 3 \} = 0$

and the result follows.

$\Box \,$ .

## References.

[1] Deutsch, E., & Sagan, B. E. (2006). Congruences for Catalan and Motzkin numbers and related sequences. Journal of Number Theory, 117(1), 191–215. http://doi.org/10.1016/j.jnt.2005.06.005

This note will establish formulae for the asymptotic densities in the natural numbers of two sets of numbers.  These sets are $S_{1}(\, q, r, s, t )\, = \{ (\, qi + r )\, q^{sj + t} : i, j \in \mathbb{N} \} \quad$

and

$S_{2}(\, q, r, s, t )\, = \{ (\, qi + r )\, q^{sj + t} : i, j \in \mathbb{N}, j > 0 \}$

for integers $\quad q, r, s, t$.

Theorem 1. Let $\quad q, r, s, t \in \mathbb{Z} \quad$ with $\quad q, r, s > 0 \quad$ and $\quad 0 < r < q \quad$. Then the asymptotic density of the set $S_{1} \quad$ is $\quad (\, q^{t + 1 - s} (\, q^{s} - 1 )\, )\, ^{-1} \quad$. In addition the asymptotic density of the set $\, S_{2} \,$ is $\, (\, q^{t + 1} (\, q^{s} - 1 )\, )\, ^{-1}$.

Proof.

We firstly look at $S_{1}$. We have, for fixed $j \geq 0$,

$\#\{ i \geq 0: (\, qi + r)\, q^{sj + t} \leq N \} = \frac {N}{q^{qj+t+1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\,$

where $0 \leq E( \, j, N, q, r, s, t ) < 1$ is an error term introduced by not rounding down to the nearest integer. So, letting

$U(N, s, t) =: \quad \lfloor \frac {\log_q (\, N )\, - t - 1}{s} \rfloor \quad \,$,

we have

$\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \}$

$= \sum_{j \geq 0} (\, \frac {N}{q^{sj + t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\, = \sum_{j = 0}^{U} (\, \frac {N}{q^{sj+t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\,$

$= \frac {N}{q^{t + 1} } \sum_{j = 0}^{U} (\, \frac {1}{q^{s}} )\,^{j} - E^{'}(\, N, q, r, s, t )\,$

where the new error term $E^{'} (\, N, q, r, s, t )\,$ satisfies $0 < E^{'} (\, N, q, r, s, t )\, < 2(\, U + 1 )\,$.

Then

$\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \}$

$= (\, \frac {N}{q^{t+1}} )\, (\, 1 - (\, \frac {1}{q^{s}} )\, ^{U + 1} )\, (\, 1 - \frac {1}{q^{s} } )\, ^{-1} - E^{'}$

Since $\lim_{N \to \infty} \frac {E^{'}(\, N, q, r, s, t )\, }{N} = 0$ and $\lim_{N \to \infty} \frac {1}{N} (\, \frac {1}{q^{s} } )\, ^{U + 1} = 0$

$\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \}$

$= (\, q^{t + 1 - s} (\, q^{s} - 1 )\,)\, ^{-1}$.

The proof for $S_{2}$ is very similar. With $E, E^{'}$ and $U$ defined as above we have for fixed $j \geq 1$,

$\#\{ i \geq 0: (\, qi + r)\, q^{sj + t} \leq N \} = \frac {N}{q^{qj+t+1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\,$

and

$\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= \sum_{j \geq 1} (\, \frac {N}{q^{sj + t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\, = \sum_{j = 1}^{U} (\, \frac {N}{q^{sj+t + 1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\,$

$= \frac {N}{q^{t + 1 + s} } \sum_{j = 0}^{U - 1} (\, \frac {1}{q^{s}} )\,^{j} - E^{'}(\, N, q, r, s, t )\,$

$= (\, \frac {N}{q^{t+1+s}} )\, (\, 1 - (\, \frac {1}{q^{s}} )\, ^{U} )\, (\, 1 - \frac {1}{q^{s} } )\, ^{-1} - E^{'}$

and

$\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= (\, q^{t + 1 } (\, q^{s} - 1 )\,)\, ^{-1}$.

$\Box$.

The Motzkin numbers $M_n$ are defined by

$M_n := \sum_{k \geq 0} \binom {n}{2k} C_{k}$

where $C_{k}\,$ are the Catalan numbers. The following result is established in [1]

Theorem 1 (Theorem 5.5 of [1]). The nth Motzkin number $M_n$ is even if and only if $n = (4i + \epsilon)4^{j+1} - \delta$ for $i, j \in \mathbb{N}, \epsilon \in \{1, 3\}$ and $\delta \in \{1, 2\}$. Moreover, we have

$M_n \equiv 4 \mod 8$ if $(\, \epsilon, \delta )\, = (\, 1, 1 )\,$ or $(\, 3, 2 )\,$

$M_n \equiv 4y + 2 \mod 8$ if $(\, \epsilon, \delta )\, = (\, 1, 2 )\, or (\, 3, 1 )\,$

where $\, y \,$ is the number of digit 1’s in the base 2 representation of $\, 4i + \epsilon - 1$.

Remark 2. The 4 choices for $(\, \epsilon, \delta )\,$ in the above theorem give 4 disjoint sets of numbers $n = (4i + \epsilon)4^{j+1} - \delta$.

Theorem 3. Each of the 4 disjoint sets defined by the choice of $(\, \epsilon, \delta )\,$ in Theorem 1 has asymptotic density $\frac {1}{12}$ in the natural numbers.

Proof: Use the result for the set $S_{1}$ of Theorem 1 of the post here with $q = 4, r = \epsilon, s = 1, t = 1$.

$\Box \,$.

Corollary 4: The asymptotic density of

$\{ n < N: M_n \equiv 0 \mod 2 \}$ is $\frac {1}{3}$.

The asymptotic density of

$\{ n < N: M_n \equiv 4 \mod 8 \}$ is $\frac {1}{6}$.

The asymptotic density of each the sets

$\{ n < N: M_n \equiv 2 \mod 8 \}$ and $\{ n < N: M_n \equiv 6 \mod 8 \}$ is $\frac {1}{12}$.

Remark 5: The first 2 statements of Corollary 4 follows immediately from theorems 1 and 3. The third statement follows from the observation that the numbers of 1’s in the base 2 expansion of $i$ is equally likely to be odd or even and therefore the same applies the the number of 1’s in the base 2 expansion of $4i + \epsilon - 1$. Since the asymptotic density of the 2 sets combined is $\frac {1}{6}$ (from Theorems 1 and 3), each of the two sets has asymptotic density of $\frac {1}{12}$.

## Reference

[1] Eu, S.-P., Liu, S.-C., & Yeh, Y.-N. (2008). Catalan and Motzkin numbers modulo 4 and 8. European Journal of Combinatorics, 29(6), 1449–1466. http://doi.org/10.1016/j.ejc.2007.06.019

The Motzkin numbers $M_n$ are defined by

$M_n := \sum_{k \geq 0} \binom {n}{2k} C_{k}$

where $C_{k}\,$ are the Catalan numbers. The following result is established in [1]

Theorem 1 (Theorem 5.4 of [1]). The Motzkin number $M_n$ is divisible by $5$ if and only if $n$ is one of the following forms

$(\, 5i + 1 )\, 5^{2j} - 2,\, (\, 5i + 2 )\, 5^{2j-1} - 1,\, (\, 5i + 3 )\, 5^{2j-1} - 2,\, (\, 5i + 4 )\, 5^{2j} - 1$

where $i, j \in \mathbb{N}$ and $j \geq 1$.

Theorem 2: The asymptotic density of numbers of the first form in theorem 1 is $\frac {1}{120}$. Numbers of the fourth form also have asymptotic density $\frac {1}{120}$. The asymptotic density of numbers of the second and third forms in theorem 1 is $\frac {1}{24}$ each.

Corollary 3: The asymptotic density of $\#\{n < N: M_{n} \equiv 0 \mod {5} \}$ is $\frac {1}{10} \,$.

Remark 4: Corollary 3 follows immediately from theorems 1 and 2 and the disjointness of the 4 forms of integers listed in theorem 1.

Remark 5: Numerical tests also show that roughly 22.5% of Motzkin numbers are congruent to each of $1, 2, 3, 4 \mod {5}$.

Proof of Theorem 2.

Firstly consider numbers of the form $(\, 5i + 1)\, 5^{2j} - 2\,$. As we are interested in asymptotic density it is enough to look at numbers of the form $(\, 5i + 1)\, 5^{2j}\,$. We have, for fixed $j \geq 1$,

$\#\{ i \geq 0: (\, 5i + 1)\, 5^{2j} \leq N \} = \frac {N}{5^{2j+1}} - \frac {1}{5} - E(\, j, N )\,$

where $0 \leq E( \, j, N ) < 1$ is an error term introduced by not rounding down to the nearest integer. So,

$\#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= \sum_{j \geq 1} (\, \frac {N}{5^{2j+1}} - \frac {1}{5} - E(\, j, N )\, )\, = \sum_{j = 1}^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\, \rfloor} (\, \frac {N}{5^{2j+1}} - \frac {1}{5} - E(\, j, N )\, )\,$

$= \frac {N}{125} \sum_{j = 0}^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\, \rfloor - 1} (\, \frac {1}{25} )\,^{j} - E^{'}(\, N )\,$

where the new error term $E^{'} (\, N )\,$ satisfies $0 \leq E^{'} (\, N )\, < \frac{3}{5} (\, \log_{5} (\, N )\,$. Then

$\#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= (\, \frac {N}{125} )\, \frac {1 - (\, \frac {1}{25} )\,^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\, \rfloor} }{1 - \frac {1}{25} } - E^{'}(\, N )\,$.

Since $\lim_{N \to \infty} \frac {E^{'}(\, N )\, }{N} = 0$

$\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \} = \frac {1}{120}$.

A similar argument can be used to establish the asymptotic densities of the other 3 forms of numbers in the theorem.

$\Box$.

## References

[1] Deutsch, E., & Sagan, B. E. (2006). Congruences for Catalan and Motzkin numbers and related sequences. Journal of Number Theory, 117(1), 191–215. http://doi.org/10.1016/j.jnt.2005.06.005

The Catalan numbers are defined by

$C_n = \frac{1}{n + 1} \binom {2n} {n}.$

Corollary 2 of the previous post established that

$\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \sum_{i = k+1}^{i = t} \binom{t} {i}.$

This result can be used to show that the asymptotic density of the set $\#\{n < N: C_{n} \equiv 0 \mod {2^k} \}$ is $1.$

To this end let $N \in \mathbb{N}: 2^{r} \leq N < 2^{r+1}$ for some $r \in \mathbb{N}.$ Then  $r = \lfloor \log_2(\, N)\, \rfloor$ and

$\#\{n < N: d(\, \alpha (\, n )\, )\, = k \} \leq \#\{n < 2^{r+1}: d(\, \alpha (\, n )\, )\, = k \} = \binom {r+1} {k + 1}.$

So, as mentioned in the previous post

$\#\{n < N: C_{n} \equiv 0 \mod {2^k} \} = N - \#\{n < N: d(\, \alpha (\, n )\, )\, < k \}$

$= N - \sum_{i = 0}^{i = k - 1} \#\{n < N: d(\, \alpha (\, n )\, )\, = i \} \geq N - \sum_{i = 0}^{i = k - 1} \binom {r+1} {i + 1}.$

And so

$\frac {1}{N} \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} \geq 1 - \frac {1}{N} P_{k} (\, r )\,$

$= 1 - \frac {1}{N} P_{k} (\, \lfloor \log_2 (\, N )\, \rfloor )\,$

where $P_{k} (\, r )\,$ is a polynomial in $r$ of degree $k$ with coefficients depending on $k$. Since $k$ is fixed and $lim_{N \to \infty} \frac {1}{N} (\, log_2{N} )\, ^{k} = 0$ for fixed $k$ the second term above is zero in the limit and

$lim_{N \to \infty} \frac {1}{N} \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} = 1.$

This result is not surprising given the highly composite nature of the Catalan numbers. In general we would also expect that the same result holds with $2^{k}$ replaced by any natural number.

## Summary

The Catalan numbers are defined by

$C_n = \frac{1}{n + 1} \binom {2n} {n}.$

This note will use results obtained by Liu and Yeh in [1] to obtain a formula for the number of $C_n < 2^{ t }$ which are divisible by $2^{ k }$   where   $t, k \in \mathbb{N}.$

Firstly, as in [1], let the p-adic order of a positive integer n be defined by

$\omega_p(\, n )\, := max\{\alpha \in \mathbb{N} : p^{\alpha} | n\} .$

and the cofactor of n with respect to $p^{ \omega_p(\, n )\, }$  be defined by

$CF_p(\, n )\, := \frac {n} {p^{\omega_p(\, n )\,}} .$

In addition the function $\alpha : \mathbb{N} \to \mathbb{N}$  is defined by

$\alpha (\, n )\, := \frac {CF_2(\, n + 1 )\, - 1} {2}.$

For a number p, we write the base p expansion of a number n as

$[\, n ]\,_{p} = \langle n_{r} n_{r-1} ... n_{1} n_{0} \rangle$

where $n_{i} \in [\, 0, p - 1]\,$  and $n = n_{r} p^{r} + n_{r-1} p^{r-1} + ... + n_{1} p + n_{0}.$

Then the function $d : \mathbb{N} \to \mathbb{N} := d (\, n )\, = n_{r} + n_{r-1} + ... + n_{1} + n$  is the sum of the p-adic digits of a natural number n (i.e. the sum of the digits of n when n is written in base p). Here we will only be interested in the case $p = 2$ . Then

Theorem   1:  $\#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \binom {t} {k + 1}.$

Corollary   2:  $\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \sum_{i = k+1}^{i = t} \binom{t} {i}.$

Corollary   3:  $\#\{n < 2^t: C_{n} \equiv 2^{k-1} \mod {2^k} \} = \binom{t} {k}.$

## Proofs.

Proof of Theorem 1:

Let  $\alpha = \alpha (\, n )\, = \frac {CF_2(\, n + 1 )\, - 1} {2}$ .  Then

$n + 1 = 2^{s} (\, 2^{\alpha} + 1 )\,$

for some arbitrary $s \in \mathbb{N} : s \geq 0$ .  Writing $n + 1$  in base 2 we have

$[\, n + 1 ]\,_{2} = \langle [\, \alpha ]\,_{2}, 1, 0 ... 0, 0 \rangle$  where there are s  0’s at the end and $s \geq 0$  is arbitrary. So,

$[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 ... 1, 1 \rangle$  where there are s  1’s  at the end and $s \geq 0$  is arbitrary. It can be seen that $d(\, n )\, = d(\, \alpha )\, + s.$

Since $n < 2^{t}$  and  $d(\, \alpha (\, n )\, )\, = k$  the possible base 2 representations of n are

$[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0 \rangle$  with $\alpha < 2^{t - 1}$

$[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 \rangle$  with $\alpha < 2^{t - 2}$

.

.

.

$[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1, 1, ... 1 \rangle$  with $\alpha < 2^{k}$  and $(\, t - k - 1)\,$   1’s at the end.

Therefore, counting each of these possibilities and using the fact that $d (\, \alpha )\, = k$  gives

$\#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \sum_{i = k}^{i = t - 1} \binom{i} {k} = \binom{t} {k + 1}.$

$\Box$

## Proof of Corollary 2.

The following result appears in [1].

Theorem 4 (Corollary 4.3 of [1]): In general, we have $\omega_{2} (\, C_{n} )\, = d (\, \alpha )\, .$   In particular,  $C_{n} \equiv 0 (\, mod 2^{k} )\,$  if and only if  $d (\, \alpha )\, \geq k$ ,  and  $C_{n} \equiv 2^{k - 1} (\, mod 2^{k} )\,$  if and only if  $d (\, \alpha )\, = k - 1.$

Corollary 2 follows from Theorem 1 and Theorem 4 above since

$\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \#\{n < 2^t: d(\, \alpha (\, n )\, )\, \geq k \}$  from Theorem 4

$= 2^{t} - 1 - \sum_{i = 0}^{i = k - 1} \#\{n < 2^t: d(\, \alpha (\, n )\, )\, = i \}$

$= 2^{t} - 1 - \sum_{i = 0}^{i = k - 1} \binom{t} {i + 1}$  from Theorem 1

$= 2^{t} - \sum_{i = 0}^{i = k} \binom{t} {i}$

$= \sum_{i = k + 1}^{i = t} \binom{t} {i}$  since  $2^{t} = \sum_{i = 0}^{i = t} \binom{t} {i}$

$\Box$

## Proof of Corollary 3.

From Theorem 4,

$\#\{n < 2^t: C_{n} \equiv 2^{k-1} \mod {2^k} \} = \#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k - 1 \}$

$= \binom{t} {k}$  from Theorem 1.

$\Box$

## Reference

[1]  Liu, S.-C., & Yeh, J. (2010). Catalan numbers modulo $2^k$. J Integer Sequences. Vol 13 (2010) Article 10.5.4