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

Author

Jianing Song, Jan 25 2020

Keywords

• nonn
• base
• easy

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)

Examples

			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)
		

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

Crossrefs

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

Row 10 of A331787.

Programs

PARI

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

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