9
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ speaking about 6 .. i was the 6th upvoter :) cheers $\endgroup$ – Ahmad Bazzi Dec 7 '18 at 12:24
  • 1
    $\begingroup$ "Anonymizing" means... what? If you want to create a funciton that maps each 9-digit number to a different one with 9 digits as well but without 666 sequence in it - that's impossible. You don't have enough numbers on the right side.. You would have to add an extra digit but that number won't look like SSN number. $\endgroup$ – Oldboy Dec 7 '18 at 14:09
  • $\begingroup$ Just to clarify: the numbers less than 6670 containing 666 are 666, 1666, 2666, 3666, 4666, 5666, and 6660 through 6669 (16 total). So 6670 is the 6670-16 = 6654th term of your sequence, and you want a function where $f(6654) = 6670$. Is that correct? $\endgroup$ – Michael Lugo Dec 7 '18 at 14:48
  • $\begingroup$ @Oldboy The part about social security numbers is just to provide motivation for this question. Perhaps it isn't relevant. My question is about getting the arbitrary Nth term from the sequence. Though to clarify, the original goal was to turn a real SSN into a valid but fake SSN, both groups follow the same rules (including the 666 one), thus are the same size. $\endgroup$ – Daffy Dec 7 '18 at 21:30
  • $\begingroup$ @MichaelLugo Correct $\endgroup$ – Daffy Dec 7 '18 at 21:30
4
$\begingroup$

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*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.