Is it possible to mathematically skip numbers containing 666?

Question

I once had a project which involved taking actual real social security numbers and anonymizing them into unique real-looking fake SSNs. One of the rules for SSNs is that it cannot contain a run of 666 inside it. That raised the question, is it possible to do this mathematically?

More generally, given this sequence

$$S = 1, 2, 3, ..., 665, 667, 668, ..., 1665, 1667, ..., 6658, 6659, 6670, ...$$

Is it possible to get the $n$th term without simply counting up to it?

Answer 1

A partial answer: This approach is based upon generating functions. Let $S(m)$ denote the positive integers $\leq m$ which do not contain three consecutive $6$. We calculate $S(m)$ for powers of $10$ and show the following is valid for $n\geq 0$:

\begin{align*} S\left(10^n\right)=1+\sum_{j=0}^{n}9^j\sum_{k=0}^{j+1}\binom{j+1}{k}\binom{k}{n-j-k}[[n-j\geq k]]\tag{1} \end{align*}

We use Iverson brackets $[[P]]$ in order to filter out invalid cases. Equivalently we can use $\min\{j+1,n-j\}$ as upper limit of the inner sum instead of $j+1$. We start with

Smirnov words:

We count the number of valid words of length $n$. We start considering words with no consecutive equal digits at all.

These words are called Smirnov words or Carlitz words. (See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.)

A generating function of the number of Smirnov words over the ten digits $\{0,1,2,\ldots,9\}$ is given by \begin{align*} \left(1-\frac{10z}{1+z}\right)^{-1}\tag{1} \end{align*}

Generating function: $A(z)$

• Since there are no restrictions to the digits $\{0,1,2\ldots,9\}\setminus\{6\}$, we replace occurrences of these digits in a Smirnov word by any runs with length $\geq 1$. \begin{align*} z&\longrightarrow z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{2}\\ \end{align*}

• Since we are allowed to use runs of $6$ up to length $2$ we substitute \begin{align*} z&\longrightarrow z+z^2\tag{3}\\ \end{align*}

We obtain by substituting (2) and (3) in (1) a generating function $A(z)=\sum_{n=0}^\infty a_nz^n$ \begin{align*} A(z)&=\left(1-9\cdot\frac{\frac{z}{1-z}}{1+\frac{z}{1-z}}-\frac{z+z^2}{1+z+z^2}\right)^{-1}\\ &=\frac{1+z+z^2}{1-9z(1+z+z^2)}\tag{4}\\ &=1+10z+100z^2+999z^3+\color{blue}{9\,981}z^4+99\,720z^5\cdots\tag{5} \end{align*} with $a_n$ giving the number of all words of length $n$ consisting of the $10$ digits $0-9$ having no substring $666$. The coefficient in (5) were calculated with some help of Wolfram Alpha.

Example: $n=4$:

The number of strings of length $4$ is given as $\color{blue}{9\,981}$ which counts the $10\,000$ words of length $4$ minus the following $19$ words: \begin{align*} 0666\ 1666\ 2666\ 3666\ 4666\ 5666\ 6666\ 7666\ 8666\ 9666\\ 6660\ 6661\ 6662\ 6663\ 6664\ 6665\ \ \qquad 6667\ 6668\ 6669 \end{align*}

We don't want to count words with leading zeros. Denoting with $[z^n]$ the coefficient of $z^n$ of a series we have to subtract $[z^{3}]A(z)$.

The number of valid words of length $4$ is \begin{align*} \left([z^4]-[z^{3}]\right)A(z)=9\,981-999=8\,982 \end{align*}

The number of all valid words of length $\leq 4$ is even simpler, since it is \begin{align*} &\left([z^4]-[z^{3}]\right)A(z)+\left([z^3]-[z^{2}]\right)A(z)+\left([z^2]-[z^{1}]\right)A(z)\\ &\qquad+\left([z^1]-[z^{0}]\right)A(z)+[z^0]A(z)\\ &\qquad=[z^4]A(z)\\ &\qquad\color{blue}{=9\,981} \end{align*}

We conclude \begin{align*} \color{blue}{S(10^4)}=1+S(9999)=1+[z^4]A(z)\color{blue}{=9\,982}\tag{6} \end{align*} and an general we have $S(10^n)=1+[z^n]A(z)$ for $n\geq 0$.

Calculation of $S(10^n)$:

In order to find an explicit formula for $S(10^n)$ we calculate the coefficient $[z^n]A(z)$ from the representation (4). We obtain \begin{align*} \color{blue}{[z^n]}&\color{blue}{\frac{1+z+z^2}{1-9z(1+z+z^2)}}\\ &=[z^n]\sum_{j=0}^\infty9^jz^j(1+z+z^2)^{j+1}\tag{7}\\ &=\sum_{j=0}^n9^j[z^{n-j}](1+z(1+z))^{j+1}\tag{8}\\ &=\sum_{j=0}^n9^j[z^{n-j}]\sum_{k=1}^{j+1}\binom{j+1}{k}z^k(1+z)^k\tag{9}\\ &=\sum_{j=0}^n9^j\sum_{k=0}^{j+1}\binom{j+1}{k}[z^{n-j-k}](1+z)^k[[n-j\geq k]]\tag{10}\\ &\,\,\color{blue}{=\sum_{j=0}^n9^j\sum_{k=0}^{j+1}\binom{j+1}{k}\binom{k}{n-j-k}[[n-j\geq k]]}\tag{11} \end{align*}

We conclude \begin{align*} S(10^n)=1+\sum_{j=0}^n9^j\sum_{k=0}^{j+1}\binom{j+1}{k}\binom{k}{n-j-k}[[n-j\geq k]] \end{align*} and the claim (1) follows.

Comment:

• In (7) we use the geometric series expansion.

• In (8) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$ and restrict the upper limit of the sum with $n$ since greater indices do not contribute to the coefficient of $z^n$.

• In (9) we expand the binomial.

• In (10) we apply the rule as we did in (8) and ensure with the help of the Iverson brackets that the power $n-j-k$ of $z$ is non-negative.

• In (11) we finally select the coefficient of $z^{n-j-k}$.

Example $n=4$ revisited:

We can now calculate $S(10^4)$ without the help of Wolfram Alpha and obtain \begin{align*} \color{blue}{[z^4]A(z)}&=\sum_{j=0}^49^j\sum_{j=0}^{j+1}\binom{j+1}{k}\binom{k}{4-j-k}[[4-j\geq k]]\\ &=9^0\sum_{k=0}^1\binom{1}{k}\binom{k}{4-k}+9^1\sum_{k=0}^2\binom{2}{k}\binom{k}{3-k}+9^2\sum_{k=0}^2\binom{3}{k}\binom{k}{2-k}\\ &\qquad+9^3\sum_{k=0}^1\binom{4}{k}\binom{k}{1-k}+9^4\sum_{k=0}^0\binom{5}{k}\binom{k}{0-k}\\ &=9^0\left[\binom{1}{0}\binom{0}{4}+\binom{1}{1}\binom{1}{3}\right] +9^1\left[\binom{2}{0}\binom{0}{3}+\binom{2}{1}\binom{1}{2}+\binom{2}{2}\binom{2}{1}\right]\\ &\qquad +9^2\left[\binom{3}{0}\binom{0}{2}+\binom{3}{1}\binom{1}{1}+\binom{3}{2}\binom{2}{0}\right]\\ &\qquad+9^3\left[\binom{4}{0}\binom{0}{1}+\binom{4}{1}\binom{1}{0}\right]+9^4\left[\binom{5}{0}\binom{0}{0}\right]\\ &=1[0+0]+9[0+0+2]+81[0+3+3]+729[0+4]+6\,561[1]\\ &\,\,\color{blue}{= 9\,981} \end{align*} We obtain in accordance with (6) \begin{align*} \color{blue}{S(10\,000)}&=1+[z^4]A(z)\color{blue}{=9\,982} \end{align*}