View Complete Reference

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