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
KEYWORD
nonn,base,easy
AUTHOR
Jianing Song, Jan 25 2020
STATUS
approved