A331786 a(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.

0, 2, 2, 6, 8, 8, 12, 14, 8, 18, 38, 38, 78, 98, 98, 138, 158, 98, 198, 398, 398, 798, 998, 998, 1398, 1598, 998, 1998, 3998, 3998, 7998, 9998, 9998, 13998, 15998, 9998, 19998, 39998, 39998, 79998, 99998, 99998, 139998, 159998, 99998, 199998, 399998, 399998, 799998

Offset

1,2

Comments

Write n = 9*s + t, 1 <= t <= 9. 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 = 10^(u_0) - 10^s*(t-gcd(t,9)+1) + 1, where u_0 is the smallest nonnegative solution to 9*u == -gcd(t,9) (mod n). See A331787 for more detailed information.

From Bernard Schott, Mar 25 2022: (Start)

Equivalently, a(n) is the largest number of consecutive integers whose sum of digits (A007953) is never divisible by n (this is the answer to problem of Diophante link).

a(n) ends with 8 when n = 5, 6 and n >= 9 (see formula). (End)

Links

Jianing Song, Table of n, a(n) for n = 1..1000

Diophante, A389 - Les décaXphobes (in French).

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,10,-10).

Formula

If n = 9*s + t, 1 <= t <= 9, then a(n) = 10^s*(2*t-gcd(t,9)+1) - 2. See A331787 for a proof of the formula in base b.

Conjectures from Colin Barker, Jan 26 2020: (Start)

G.f.: 2*x^2*(1 + 2*x^2 + x^3 + 2*x^5 + x^6 - 3*x^7 + 5*x^8) / ((1 - x)*(1 - 10*x^9)).

a(n) = a(n-1) + 10*a(n-9) - 10*a(n-10) for n>10.

(End) [This conjecture is correct.]

a(n) = O(10^(n/9)).

Example

The following list gives the smallest example for each 2 <= n <= 27:
   2: 9..10 (2)
   3: 1..2 (2)
   4: 997..1002 (6)
   5: 6..13 (8)
   6: 7..14 (8)
   7: 994..1005 (12)
   8: 9999993..10000006 (14)
   9: 1..8 (8)
  10: 1..18 (18)
  11: 999981..1000018 (38)
  12: 1..38 (38)
  13: 9999999961..10000000038 (78)
  14: 951..1048 (98)
  15: 961..1058 (98)
  16: 9999931..10000068 (138)
  17: 999999999999921..1000000000000078 (158)
  18: 1..98 (98)
  19: 1..198 (198)
  20: 99999999801..100000000198 (398)
  21: 1..398 (398)
  22: 99999999999999601..100000000000000398 (798)
  23: 99501..100498 (998)
  24: 99601..100598 (998)
  25: 99999999301..100000000698 (1398)
  26: 99999999999999999999201..100000000000000000000798 (1598)
  27: 1..998 (998)

Prog

(PARI) a(n) = my(s=(n-1)\9, t=(n-1)%9+1); 10^s*(2*t-gcd(t, 9)+1)-2

Crossrefs

Cf. A007953 (S(N)), A051885, A331788.

Row 10 of A331787.

Sequence in context: A099490 A167878 A351928 * A320139 A033724 A033748

Adjacent sequences: A331783 A331784 A331785 * A331787 A331788 A331789

Keyword

nonn,base,easy

Author

Jianing Song, Jan 25 2020

Status

approved