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 sigma_{m,j} = j! * S(m,j), N_m(j) = binomial(b-1, j)*sigma_{m,j} + binomial(b-1, j-1)*(sigma_{m,j} - sigma_{m-1,j} - sigma_{m-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 sum_{n < 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 sum_{n <= 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 sum_{n <= 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.
Authors
- Mark Kim (ORCID: https://orcid.org/0000-0001-7601-831X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.5281/zenodo.24151471
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint