A331787 T(b,n) is the largest m such that there exists N such that none of S(N), S(N+1), ..., S(N+m-1) is divisible by n, where S(N) is the sum of digits of N in base b. Square array read by ascending antidiagonals.

0, 0, 2, 0, 1, 6, 0, 2, 4, 14, 0, 1, 2, 7, 30, 0, 2, 4, 6, 16, 62, 0, 1, 4, 3, 14, 25, 126, 0, 2, 2, 6, 8, 14, 52, 254, 0, 1, 4, 5, 4, 13, 30, 79, 510, 0, 2, 4, 6, 8, 10, 28, 62, 160, 1022, 0, 1, 2, 3, 8, 5, 22, 23, 62, 241, 2046, 0, 2, 4, 6, 8, 10, 12, 34, 48, 126, 484, 4094

Offset

2,3

Comments

Write n = (b-1)*s + t, 1 <= t <= b-1. The smallest N_0 such that none of S(N_0), S(N_0+1), ..., S(N_0+m-1) is divisible by n is given by N_0 = b^(u_0) - b^s*(t-gcd(t,b-1)+1) + 1, where u_0 is the smallest nonnegative solution to (b-1)*u == -gcd(t,b-1) (mod n). See my link below for more detailed information.

Links

Jianing Song, Table of n, a(n) for n = 2..7627 (Note: T(b,n) occurs at the ((n+b-2)*(n+b-1)/2-b+3)-th place)

Jianing Song, Proof of the formula, and the examples N_0 such that none of S(N_0), S(N_0+1), ..., S(N_0+m-1) is divisible by n.

Formula

If n = (b-1)*s + t, 1 <= t <= b-1, then T(b,n) = b^s*(2*t-gcd(t,b-1)+1) - 2. See my link for a proof of the formula.

T(b,n) = T(b,n-1) + b*T(b,n-b+1) - b*T(b,n-b) for b >= 2, n >= b+1.

T(b,n) = O(b^(n/(b-1))).

Example

Table begins
  b\n  1  2  3   4   5   6    7    8    9    10
   2   0  2  6  14  30  62  126  254  510  1022
   3   0  1  4   7  16  25   52   79  160   241
   4   0  2  2   6  14  14   30   62   62   126
   5   0  1  4   3   8  13   28   23   48    73
   6   0  2  4   6   4  10   22   34   46    34
   7   0  1  2   5   8   5   12   19   26    47
   8   0  2  4   6   8  10    6   14   30    46
   9   0  1  4   3   8   9   12    7   16    25
  10   0  2  2   6   8   8   12   14    8    18

Prog

(PARI) T(b, n) = my(s=(n-1)\(b-1), t=(n-1)%(b-1)+1); b^s*(2*t-gcd(t, b-1)+1)-2

Crossrefs

Cf. A331789.

Cf. A000918 (row 2), A164123 (row 3), A331786 (row 10).

Sequence in context: A089627 A306534 A344392 * A321686 A055925 A276436

Adjacent sequences: A331784 A331785 A331786 * A331788 A331789 A331790

Keyword

nonn,base,easy,tabl

Author

Jianing Song, Jan 25 2020

Status

approved