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

Author

Jianing Song, Jan 25 2020

Keywords

• nonn
• base
• easy
• tabl

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.

Examples

			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
		

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.

Crossrefs

Cf. A331789.

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

Programs

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

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