Numbers Without Ones: Chorisenic Sets

Left: Count of elements of set {\mathbf{Xe}_{10}}. Right: partial density of set {\mathbf{Xe}_{10}}.

There is no end to the variety of sets of natural numbers. Sets having all sorts of properties have been studied and many more remain to be discovered. In this note we study the set of natural numbers for which the decimal digit 1 does not occur.

Google Translate on my mobile phone gives the Greek for “without ones” as {\chi\omega\rho\iota'\varsigma} {\varepsilon'\nu\alpha} or choris ena, so let us call a set of “oneless numbers” a chorisenic set.

Numerical Pattern

In the Figure above (left panel) we plot the count {\kappa(n)} of the chorisenic set for values of {n} up to {30{,}000}. In the right panel, the partial density is plotted. It will ultimately tend to zero, although this is not obvious from the plot.

For small {n}, we can easily count the numbers less than {n} that have no {1's} in their decimal expansion. Some examples are shown in the Table below. It is straightforward to show that the count {\kappa(n)} is {9^k-1} for {n=10^k}. The number {10^k} is followed by a string of numbers starting with 1, so the count for {n=2\times 10^k} is greater by just 1, at {9^k}.The partial density is defined as

\displaystyle \rho_{\mathbf{Xe}_{10}}(n) = \frac{\kappa(n)}{n} \,.

It is relatively large for {n=10^k} and drops by a factor of 2 when {n=2\times 10^k}. Thus it has an oscillating pattern. However, as {n} tends to {\infty}, the partial density tends to zero. Thus, the natural density, {\rho_{\mathbf{Xe}_{10}}(n) = \lim_{n\rightarrow\infty} [{\kappa(n)}/{n}]} is zero.

Probability Argument

The ultimate limit of the density can easily be understood in terms of probability (Tenenbaum, 1995). Let us consider the set of all numbers having up to {K} digits. That is, all numbers less than {N = 10^{K+1}}. For a randomly chosen number {n}, an arbitrary digit may take any of the ten possible values {\{0, 1, 2, 3, 4, 5, 6, 7, 8 , 9\}} and we may assume each value is equally likely. Thus, the probability of an arbitrary digit not being 1 is {9/10}. Since we may assume that the digits are independently chosen, the overall probability {P} that 1 does not appear anywhere in the number is

\displaystyle P \equiv \mbox{Probability that no 1's appear} = \left( \frac{9}{10} \right)^K \,.

Of course, if the cut-off is at {N = 2\times10^{K+1}}, the probability is halved. In any case, it is clear that {P \rightarrow 0} as {N\rightarrow\infty}.

Ternary Chorisenic Set {\mathbf{Xe}_{3}}

We can follow the above procedure but starting with numbers expressed in base 3. For these numbers the only admissible digits are {\{0, 1, 2\}}. We consider the set of all natural numbers whose ternary expansions do not contain any digits equal to 1.

According to, the first {2^n} terms of the sequence {\mathbf{Xe}_3} can be obtained using the Cantor process of “middle-third-removal” for the segment {[0,3^{n}-1]}. For example, if {n=2} we get

\displaystyle \begin{array}{rcl} &[0,1,2,3,4,5,6,7,8]& \\ &[0,1,2,\bullet,\bullet,\bullet,6,7,8]& \\ &[0,\bullet,2,\bullet,\bullet,\bullet,6,\bullet,8]& \end{array}

The numbers remaining are the initial elements of {\mathbf{Xe}_3}. A more complete list of initial terms (from OEIS A005823) is

\displaystyle \begin{array}{rcl} & 0, 2, 6, 8, 18, 20, 24, 26, 54, 56, 60, 62, 72, 74, 78, 80, 162, 164, 168, \\ & 170, 180, 182, 186, 188, 216, 218, 222, 224, 234, 236, 240, 242, \dots \end{array}

This gives 16 terms (including 0) less than {81 = 3^4}. The OEIS page suggests that the terms of the sequence could be called “Cantor’s numbers”.

The total of numbers with {k} or fewer ternary digits is {3^k}. The number of these with no digits equal to {1} can be shown to be {2^{k}-1}. Thus, the partial density of the set of numbers with no digit equal to {1} is

\displaystyle \rho = \frac{2^{k}-1}{3^k} \approx \left( \frac{2}{3} \right)^k \,.

This becomes smaller as {k} becomes larger and the natural density of the set {\mathbf{Xe}_3} is zero.

Left: count of elements of set {\mathbf{Xe}_{3}} for {n\le 3^8}. Right: partial density of set {\mathbf{Xe}_{3}}.

In the Figure above we show the count of elements of the set {\mathbf{Xe}_{3}} (left) and its partial density (right). We see that the count is constant most of the time, with isolated jumps. In fact, this set is intimately related to the Cantor Ternary Set, the set of real numbers in {[0,1]} containing no {1's} in their ternary expansion. This set is fractal in nature, of Hausdorff dimension {\log 2/\log 3}, uncountable and yet having Lebesgue measure zero.

Readers may enjoy exploring the relationship between {\mathbf{Xe}_{3}} and Cantor’s set.


{\bullet} The On-Line Encyclopedia of Integer Sequences (OEIS): Numbers whose ternary expansion contains no 1’s.

{\bullet} Tenenbaum, Gérald, 1995: Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press. ISBN 0-521-41261-7.

\star \qquad \star \qquad \star

Collection of ThatsMaths Articles
From   Logic PressAvailable also in hardback form 

Last 50 Posts