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,5

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}.

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

Wikipedia, Kummer's_theorem

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.

Example

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

Prog

(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))

Crossrefs

Cf. A022998 (2nd row), A062383 (2nd column), A349221.

Sequence in context: A120013 A344180 A151847 * A179743 A113749 A109225

Adjacent sequences: A349590 A349591 A349592 * A349594 A349595 A349596

Keyword

nonn,tabl,easy

Author

Jianing Song, Nov 27 2021

Status

approved