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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Mark Kim
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

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

Mark Kim
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon