Combinatorical and Algebraic Structures Seminar

Session details

Date: 13.5.2014
Speaker: Kevin Hare, University of Waterloo, Canada
Title: Base $d$ expansions with digits $0$ to $q-1$
Abstract: Let $d$ and $q$ be positive integers, and consider representing a positive integer $n$ with base $d$ and digits $0, 1, \cdots, q-1$. If $q < d$, then not all positive integers can be represented. If $q = d$, every positive integer can be represented in exactly one way. If $q > d$, then there may be multiple ways of representing the integer $n$. Let $f_{d,q}(n)$ be the number of representations of $n$ with base $d$ and digits $0, 1, \cdots, q-1$. For example, if $d = 2$ and $q = 7$ we might represent 6 as $(110)_2 = 1 \cdot 2^2 + 1 \cdot 2^1 + 0 \cdot 2^0$ as well as $(102)_2 = 1 \cdot 2^2 + 0 \cdot 2^1 + 2 \cdot 2^0$. In fact, there are six representations in this case $(110)_2, (102)_2, (30)_2, (22)_2, (14)_2$ and $(6)_2$, hence $f_{2,7}(6) = 6$. In this talk we will discuss the asymptotics of $f_{d,q}(n)$ as $n\to \infty$. This depends in a rather strange way on the Generalized Thue-Morse sequence. While many results are computationally/experimentally true, only partial results are known.

Return to index.