A348884 Number of pairs of base-p digits for which binomial coefficients support a Lucas congruence modulo p^2, where p is the n-th prime.

1, 3, 3, 4, 9, 4, 6, 4, 3, 9, 4, 16, 6, 10, 3, 9, 3, 10, 4, 6, 10, 4, 3, 3, 10, 3, 7, 3, 22, 9, 4, 3, 9, 7, 3, 4, 4, 4, 3, 9, 12, 4, 6, 7, 3, 10, 10, 7, 21, 4, 3, 3, 4, 3, 9, 3, 9, 10, 4, 3, 4, 3, 4, 3, 10, 3, 13, 4, 15, 4, 12, 9, 7, 7, 13, 3, 3, 10, 9, 10, 3

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

Cf. A001008, A002805.

A348883 is the analogous sequence for the Apéry numbers.

Sequence in context: A197409 A197431 A197672 * A284115 A183501 A086239

Adjacent sequences: A348881 A348882 A348883 * A348885 A348886 A348887

Keyword

nonn

Author

Eric Rowland, Nov 02 2021

Status

approved