A348884 - OEIS

%I #15 Nov 30 2021 02:46:48

%S 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,

%T 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,

%U 3,10,3,13,4,15,4,12,9,7,7,13,3,3,10,9,10,3

%N 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.

%C 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.

%C 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.

%C 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.

%H Eric Rowland, <a href="/A348884/b348884.txt">Table of n, a(n) for n = 1..256</a>

%H Édouard Lucas, <a href="https://doi.org/10.24033/bsmf.127">Sur les congruences des nombres eulériens et des coefficients différentiels des functions trigonométriques, suivant un module premier</a>, Bulletin de la Société Mathématique de France 6 (1878) 49-54.

%H Eric Rowland, <a href="https://arxiv.org/abs/2006.11701">Lucas' theorem modulo p^2</a>, arXiv preprint arXiv:2006.11701 [math.NT], 2020.

%e 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).

%t 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]]}]

%Y Cf. A001008, A002805.

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

%K nonn

%O 1,2

%A _Eric Rowland_, Nov 02 2021