A349593 Square array read by downward diagonals: for n >= 0, k >= 1, T(n,k) is the period of {binomial(N,n) mod k: N in Z}.

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 3, 4, 1, 1, 5, 8, 9, 8, 1, 1, 6, 5, 8, 9, 8, 1, 1, 7, 12, 5, 16, 9, 8, 1, 1, 8, 7, 36, 5, 16, 9, 8, 1, 1, 9, 16, 7, 72, 25, 16, 9, 16, 1, 1, 10, 9, 16, 7, 72, 25, 16, 9, 16, 1, 1, 11, 20, 27, 32, 7, 72, 25, 32, 27, 16, 1

Offset: 0

Author

Jianing Song, Nov 27 2021

Keywords

• nonn
• tabl
• easy

Comments

Since binomial(N,n) is defined for all integers N, there is no need to assume that N >= n.

Let Q(N) = 1 if k | binomial(N,n), 0 otherwise. Then T(n,k) is also the period of {Q(N): N in Z}.

By the formula given below, the n-th row is identical to the (n-1)th row if and only if n is not a power of a prime, i.e., n is in A024619. - Jianing Song, Jul 03 2025

Examples

			Rows 0..10:
  1,  1,  1,  1,  1,   1,  1,  1,  1,   1, ...
  1,  2,  3,  4,  5,   6,  7,  8,  9,  10, ...
  1,  4,  3,  8,  5,  12,  7, 16,  9,  20, ...
  1,  4,  9,  8,  5,  36,  7, 16, 27,  20, ...
  1,  8,  9, 16,  5,  72,  7, 32, 27,  40, ...
  1,  8,  9, 16, 25,  72,  7, 32, 27, 200, ...
  1,  8,  9, 16, 25,  72,  7, 32, 27, 200, ...
  1,  8,  9, 16, 25,  72, 49, 32, 27, 200, ...
  1, 16,  9, 32, 25, 144, 49, 64, 27, 400, ...
  1, 16, 27, 32, 25, 432, 49, 64, 81, 400, ...
  1, 16, 27, 32, 25, 432, 49, 64, 81, 400, ...
Example showing that T(4,4) = 16: for N == 0, 1, ..., 15 (mod 16), binomial(N,4) == {0, 0, 0, 0, 1, 1, 3, 3, 2, 2, 2, 2, 3, 3, 1, 1} (mod 4).
Example showing that T(3,10) = 20: for N == 0, 1, ..., 19 (mod 20), binomial(N,3) == {0, 0, 0, 1, 4, 0, 0, 5, 6, 4, 0, 5, 0, 6, 4, 5, 0, 0, 6, 9} (mod 10).
		

Links

• Jianing Song, Table of n, a(n) for antidiagonals 1..100 (T(n,k) occurs at the ((n+k)*(n+k-1)/2+n)-th place)
• Andrew Granville, Arithmetic Properties of Binomial Coefficients I: Binomial Coefficients modulo prime powers
• Jianing Song, Proof for my formula for A349593
• Jianing Song, A more simple proof of the formula for A349593
• Wikipedia, Kummer's_theorem

Crossrefs

Cf. A022998 (row n = 2), A385555 (row n = 3), A385556 (row n = 4), A385557 (rows n = 5 and 6), A385558 (row n = 7), A385559 (row n = 8), A385560 (rows n = 9 and 10).

Cf. A062383 (2nd column), A064235 (3rd column if offset 0), A385552 (5th column), A385553 (6th column), A385554 (10th column).

Cf. A349221.

Programs

Mathematica

A349593[n_, k_] := If[n == 0 || k == 1, 1, k*Product[p^Floor[Log[p, n]], {p, FactorInteger[k][[All, 1]]}]];
Table[A349593[k - 1, n - k + 2], {n, 0, 15}, {k, n + 1}] (* Paolo Xausa, Jul 07 2025 *)

PARI

T(n,k) = if(n==0, 1, my(r=1, f=factor(k)); for(j=1, #f[, 1], my(p=f[j, 1], e=f[j, 2]); r *= p^(logint(n,p)+e)); return(r))

Formula

The n-th row is multiplicative with T(n,p^e) = 1 if n = 0, p^(e+floor(log(n)/log(p))) otherwise. In other words, for n > 0, T(n,k) = k * Product_{prime p|k} p^(floor(log(n)/log(p))). See my pdf file for a proof.