OFFSET
1,2
COMMENTS
Lucas showed that binomial(p a + r, p b + s) = binomial(a, b) * binomial(r, s) mod p for all a >= 0, b >= 0, and r, s in the set {0, 1, ..., p - 1}. a(n) is the number of such pairs (r, s) for which this congruence also holds modulo p^2 for all a >= 0 and b >= 0, where p is the n-th prime.
Equivalently, a(n) is the number of pairs (r, s) of integers such that 0 <= s <= r <= p - 1 and H(r) = H(r - s) = H(s) mod p, where H(n) is the n-th harmonic number and p is the n-th prime.
Equivalently, a(n) is the number of pairs (r, s) of integers such that 0 <= s <= r <= p - 1 and binomial(r, s) = (-1)^(r - s) * binomial(p - 1 - s, r - s) = (-1)^s * binomial(p - 1 - r + s, s) mod p^2, where p is the n-th prime.
LINKS
Eric Rowland, Table of n, a(n) for n = 1..256
Édouard Lucas, Sur les congruences des nombres eulériens et des coefficients différentiels des functions trigonométriques, suivant un module premier, Bulletin de la Société Mathématique de France 6 (1878) 49-54.
Eric Rowland, Lucas' theorem modulo p^2, arXiv preprint arXiv:2006.11701 [math.NT], 2020.
EXAMPLE
The 4th prime is 7, and there are a(4) = 4 pairs (r, s) such that binomial(7 a + r, 7 b + s) = binomial(a, b) * binomial(r, s) mod 7^2 for all a >= 0 and b >= 0: (0, 0), (4, 2), (6, 0), and (6, 6).
MATHEMATICA
Table[Length[Select[Tuples[Range[0, p - 1], 2], Apply[Function[{r, s}, s <= r && Equal @@ Expand[HarmonicNumber[{r, r - s, s}], Modulus -> p]]]]], {p, Prime[Range[20]]}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Eric Rowland, Nov 02 2021
STATUS
approved