Consider n!. We know that it cannot be a perfect square since, by Bertrand’s Postulate, there is a prime p between n/2 and n. The power of p dividing n! is then 1. Brocard’s problem asks for values of n and m such that n! + 1 = m^2. So far only three pairs of numbers (n, m) are known to satisfy Brocard’s problem, namely, (4,5), (5,11), and (7,71). Such numbers are called Brown numbers. It has been conjectured that these are the only Brown numbers and this has been verified numerically up to a large value of n.

A variant on Brocard’s problem asks whether, for any fixed integer A, there are solutions (n, m) to the equation n! + A = m^2. If the abc-conjecture is true then there are only finitely many solutions for each fixed A.

Suppose A = -B^2 for some B > 0. Then n! = B^2 + x^2 is a sum of two squares. This is only possible if the power of each prime congruent to 3 (mod 4) dividing n! is even. However, Erdos proved that there is a prime p: n/2 < p < n and p = 3 (mod 4). The power of p dividing n! must be 1. Hence if A = – B^2, there are no solutions to the equation n! + A = m^2.

If A is not a square, then there is a monotonically increasing function f and a prime p <= f(A), such that A is a not a quadratic residue mod p. For this value of A and prime p, if the equation n! + A = m^2 has a solution (n, m), n must be < p; otherwise A = m^2 mod p which is impossible since A is not a quadratic residue mod p. Then, n < p <= f(A), which implies A >= f^{-1}(n) since f is increasing. In summary, if m is an integer, either m^2 – n! >= f^{-1} (n), or m^2 – n! is a perfect square.

There is a striking similarity between the songs “Music of Goodbye” from John Barry’s soundtrack to “Out of Africa” and Andrew Lloyd Webber’s “Music of the Night” from “Phantom of the Opera”. Barry’s soundtrack was released in 1985 and “Phantom of the Opera” was first performed in 1986 though the song may have been written earlier. I have not been able to find any evidence of legal action related to the similarity. However, there is a possibility that both composers used a melody from Puccini’s 1910 opera “La fanciulla del West” as the basis for their songs. The following is from Wikipedia’s entry on “Phantom of the Opera”:

Due to similarities between the song and a recurring melody in Giacomo Puccini’s 1910 opera La fanciulla del West (The Girl of the Golden West), the Puccini estate filed lawsuit against Webber, accusing him of plagiarism. An agreement was settled out of court and details were not released to the public.

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

When you enter an empty train carriage do you choose to sit on the left or right side? Do you sit facing the direction in which the train is travelling or facing the direction from which the train is coming?
I think it is fairly clear that most people prefer to sit “facing forward” and some people claim “facing backwards” makes them ill. Observation also suggests that people also have a preference for the side of the carriage on which they sit. I have not tested this, but have observed that people prefer to sit on the left side of the carriage with their right side closest to the middle aisle. It is a matter of speculation as to why this should be the case. It may be a security instinct. I recall reading that the British originally established left hand travel on roads to allow travellers to have their right arm free to defend themselves when they passed people coming from the opposite direction. Perhaps a similar instinct makes people choose to sit on the left side of trains. Of course this would indicate that left handed people should have a preference for the right side of the carriage.
There is also a subsection of people ( I don’t know how large) who prefer to sit in one of the four corners of the carriage with their back to the carriage wall so that they are facing into the carriage. I don’t know if security, politeness or some other reason is responsible for this preference. Was it Doc Holliday who would always sit with his back to the wall facing the door when in a pub?