Distinct digits of integers in base 3 and in any base: closed forms, exact counting and an O(log N) algorithm for the sequence A043530

Let a_b(n) be the number of distinct digits of n in base b; a_3 is A043530. We prove that a_3 is 3-automatic with a 7-letter morphism. For every base b >= 2 we count the m-digit integers with exactly j distinct digits in closed form through the surjection numbers sigmam,j = j! * S(m,j), N_m(j) = binomial(b-1, j)*sigmam,j + binomial(b-1, j-1)*(sigmam,j - sigmam-1,j - sigmam-1,j-1), with N_m(2) = 2^(m+1) - 4 and N_m(3) = 2*3^(m-1) - 2^(m+1) + 2 in base 3. The sum of a_b over the integers with m digits is (b-1)*(b^m - (b-1)^m), whence sumn < 3^k a_3(n) = 3^(k+1) - 2^(k+2) + 1. For arbitrary N we compute #{n <= N : a_b(n) = j} in O(b log_b N) arithmetic operations and sumn <= N a_b(n) by a direct formula through the integers that miss a given digit in O(b log_b N) operations without binomial coefficients; the n-th integer with at most j distinct digits is found in O(b log n) steps. The number of n <= x with fewer than three ternary digits lies between 2*x^(log_3 2) - 2*log_3(x) - 4 and 8*x^(log_3 2). The sum sumn <= 10^1000 a_3(n) takes 6.4 ms; the table of a_3(n) for n < 3^18 is built in 0.51 s in C and 2.9 s in NumPy, against 1.26 s for 1.6*10^6 terms by the definition in a Python loop.