### He, X, Hildebrand, AJ, Li, Y and Zhang, Y (2018)

#### Complexity of Leading Digit Sequences

Preprint in arXiv:1804.00221 [math.NT]; last accessed October 23, 2018.

**ISSN/ISBN:** Not available at this time.
**DOI:** Not available at this time.

**Abstract:** Let Sa,b denote the sequence of leading digits of an in base b. It is well known that if a is not a rational power of b, then the sequence Sa,b satisfies Benford's Law; that is, digit d occurs in Sa,b with frequency logb(1+1/d), for d=1,2,…,b−1.
In this paper, we investigate the \emph{complexity} of such sequences. We focus mainly on the \emph{block complexity}, pa,b(n), defined as the number of distinct blocks of length n appearing in Sa,b. In our main result we determine pa,b(n) for all squarefree bases b≥5 and all rational numbers a>0 that are not integral powers of b. In particular, we show that, for all such pairs (a,b), the complexity function pa,b(n) is \emph{linear}, i.e., satisfies pa,b(n)=ca,bn+da,b for all n≥1, with coefficients ca,b≥1 and da,b≥0, given explicitly in terms of a and b. We also show that the requirement that b be squarefree cannot be dropped: If b is not squarefree, then there exist integers a with 1

**Bibtex:**

```
@ARTICLE{,
author = {{He}, Xinwei and {Hildebrand}, A.~J. and {Li}, Yuchen and {Zhang}, Yunyi},
title = {Complexity of Leading Digit Sequences},
journal = {ArXiv e-prints},
archivePrefix = {arXiv},
eprint = {1804.00221},
primaryClass = {math.NT},
year = {2018},
month = {mar},
url = {https://arxiv.org/abs/1804.00221},
}
```

**Reference Type:** Preprint

**Subject Area(s):** Analysis, Probability Theory