Triskaidekaphobic passcodes

The number 13 is sometimes considered inauspicious in certain cultures and so it is not uncommon for superstitious triskaidekaphobic persons to avoid the use of 13 in their daily life and ask:

How many different lucky \(n\)-digit numeric passcodes can be formed such that they do not contain 13.

The special case of \(n = 4\) is actually a problem in the 2019 SPM additional mathematics paper (Paper 1, Question 22). For the uninitiated, this special case of \(n = 4\) can be quite intimidating.

Four-digit numeric passcode on a iOS device

To get our engine started, let's consider the first trival case when \(n = 1\). Apparently there is no single-digit passcode which contains the pattern 13 or \(\mathbb{S}_{\rm unlucky}^{(1)} = \varnothing\). Thus we do not have any unlucky passcodes when \(n = 1\):

$$n(\mathbb{S}^{(1)}_{\rm unlucky}) = 0, \quad n(\mathbb{S}^{(1)}_{\rm lucky}) = 10^1 - n(\mathbb{S}_{\rm unlucky}^{(1)}) = 10$$

where \(n(\mathbb{S}^{(n)}_{\rm lucky})\) and \(n(\mathbb{S}^{(n)}_{\rm unlucky})\) is the number of lucky and unlucky \(n\)-digit passcodes, respectively.

Unlucky passcode	Lucky passcode
0 (😅 no unlucky passcodes!)	10

The next trivial case is when \(n = 2\). For a two-digit passcode, apparently you only need to avoid the number 13 itself. So the set of unlucky passcode is \(\mathbb{S}^{(2)}_{\rm unlucky} = \{13\}\) and the set of lucky passcodes is \(\mathbb{S}^{(2)} \setminus \mathbb{S}^{(2)}_{\rm unlucky}\), therefore

$$n(\mathbb{S}_{\rm unlucky}^{(2)}) = 1, \quad n(\mathbb{S}_{\rm lucky}^{(2)}) = 10^2 - n(\mathbb{S}_{\rm unlucky}^{(2)}) = 99$$

where \(\mathbb{S}^{(n)}\) is the set of all possible \(n\)-digit passcodes.

Unlucky passcode	Lucky passcode
1 (i.e. 13 itself!)	99 (i.e. other than 13)

Next, let's move on to the next special case of \(n = 3\). The total number of possible passcode is now \(10^3\), therefore it may be useful to subdivide the passcodes into 10 equal blocks (each with 100 passcodes).

	Passcode	Unlucky passcode
I	0DD	\(n(\mathbb{S}^{(3)}_{\rm 0DD}) = n(\mathbb{S}_{\rm unlucky}^{(2)}) = 1\)
II	1DD	\(n(\mathbb{S}^{(3)}_{\rm 1DD}) + n(\mathbb{S}^{(3)}_{\rm 13D})= n(\mathbb{S}_{\rm unlucky}^{(2)}) + 10 = 11\)
III	2DD	\(n(\mathbb{S}^{(3)}_{\rm 2DD}) + n(\mathbb{S}_{\rm unlucky}^{(2)}) = 1\)
\(\vdots\)	\(\vdots\)	\(\vdots\)
X	9DD	\(n(\mathbb{S}^{(3)}_{\rm 9DD}) = n(\mathbb{S}_{\rm unlucky}^{(2)}) = 1\)

Notice that with the exception of Block II, the number of unlucky passcodes in all other blocks is identical to the special case of \(n = 2\). For Block II, since the first digit is 1, it is unlucky to have \(3\) placed in the second-digit position, and apparently there are 10 such unlucky passcodes (associated with \(\mathbb{S}_{\rm 13D}^{(3)}\)) besides 113 (the only passcode in \(\mathbb{S}_{\rm 1DD}^{(3)}\)). Thus for the special case of \(n = 3\), the number of unlucky number is given by $$\begin{align}n(\mathbb{S}_{\rm unlucky}^{(3)}) &= q_1 \times n(\mathbb{S}_{\rm unlucky}^{(2)}) + n(\mathbb{S}^{(3)}_{\rm 13D}) = 20\\ n(\mathbb{S}_{\rm lucky}^{(3)}) &= 10^3 - n(\mathbb{S}_{\rm unlucky}^{(3)}) = 980\end{align}$$ where \(q_1 = 10\) is the number of possible way to fill up the first digit, and \(n(\mathbb{S}^{(3)}_{\rm 13D}) = 10\) is the number of ways of the fill up the third digit given the second digit is 3.

Venn diagram to illustrate \(n(\mathbb{S}_{\rm 1DDD}^{(4)} \cap \mathbb{S}_{\rm 13DD}^{(4)}) = 1\)

Let's now turn our attention to the special case where \(n = 4\). Again, we will reapply the earlier strategy of subdividing the passcode population into 10 blocks. This time, each block contains 1000 passcodes:

	Passcode	Unlucky passcode
I	0DDD	\(n(\mathbb{S}^{(4)}_{\rm 0DDD}) = n(\mathbb{S}_{\rm unlucky}^{(3)}) = 20\)
II	1DDD	\(n(\mathbb{S}^{(4)}_{\rm 1DDD}) + n(\mathbb{S}_{\rm 13DD}^{(4)}) - n(\mathbb{S}^{(4)}_{\rm 1DDD} \cap \mathbb{S}_{\rm 13DD}^{(4)} )\)
III	2DDD	\(n(\mathbb{S}^{(4)}_{\rm 2DDD}) = n(\mathbb{S}_{\rm unlucky}^{(3)}) = 20\)
\(\vdots\)	\(\vdots\)	\(\vdots\)
X	9DDD	\(n(\mathbb{S}^{(4)}_{\rm 9DDD}) = n(\mathbb{S}_{\rm unlucky}^{(3)}) = 20\)

Therefore, we can write:

$$\begin{align} n(\mathbb{S}_{\rm unlucky}^{(4)}) &= q_1 \times n(\mathbb{S}_{\rm unlucky}^{(3)}) + n(\mathbb{S}_{\rm 13DD}^{(4)}) - n(\mathbb{S}^{(4)}_{\rm 1DDD} \cap \mathbb{S}_{\rm 13DD}^{(4)})\\ &= 10 \times n(\mathbb{S}_{\rm unlucky}^{(3)}) + 10^2 - n(\mathbb{S}_{\rm unlucky}^{(2)}) \\&= 10 \times 20 + 10^2 - 1\\ &= 299\\ n(\mathbb{S}_{\rm lucky}^{(4)}) &= 10^4 - n(\mathbb{S}_{\rm unlucky}^{(4)}) \\ &= 9701 \end{align}$$

Let's now repeat the analysis for \(n = 5\):

	Passcode	Unlucky passcode
I	0DDDD	\(n(\mathbb{S}^{(5)}_{\rm 0DDDD}) = n(\mathbb{S}_{\rm unlucky}^{(5)}) = 299\)
II	1DDDD	\(n(\mathbb{S}^{(5)}_{\rm 1DDDD}) + n(\mathbb{S}_{\rm 13DDD}^{(5)}) - n(\mathbb{S}^{(5)}_{\rm 1DDDD} \cap \mathbb{S}_{\rm 13DDD}^{(5)} )\)
III	2DDDD	\(n(\mathbb{S}^{(5)}_{\rm 2DDDD}) = n(\mathbb{S}_{\rm unlucky}^{(5)}) = 299\)
\(\vdots\)	\(\vdots\)	\(\vdots\)
X	9DDDD	\(n(\mathbb{S}^{(5)}_{\rm 9DDDD}) = n(\mathbb{S}_{\rm unlucky}^{(5)}) = 299\)

$$\begin{align} n(\mathbb{S}_{\rm unlucky}^{(5)}) &= q_1 \times n(\mathbb{S}_{\rm unlucky}^{(4)}) + n(\mathbb{S}_{\rm 13DDD}^{(5)}) - n(\mathbb{S}^{(5)}_{\rm 1DDDD} \cap \mathbb{S}_{\rm 13DDD}^{(5)})\\ &= 10 \times n(\mathbb{S}_{\rm unlucky}^{(4)}) + 10^3 - n(\mathbb{S}_{\rm unlucky}^{(3)}) \\&= 10 \times 299 + 10^3 - 20\\ &= 3970\\ n(\mathbb{S}_{\rm lucky}^{(5)}) &= 10^4 - n(\mathbb{S}_{\rm unlucky}^{(5)}) \\ &= 96030 \end{align}$$

By now, I suppose you are able to see some pattern in the analysis for the special cases of 2, 3, 4, and 5. It seems like the following is always true:

$$n(\mathbb{S}^{(n)}_{\rm unlucky}) = 10 \cdot n(\mathbb{S}^{(n-1)}_{\rm unlucky}) + 10^{n-2} - n(\mathbb{S}^{(n - 2)}_{\rm unlucky})$$ And therefore for \(n = 6\), we must have: $$n(\mathbb{S}^{(6)}_{\rm unlucky}) = 10\times 9701 + 10^4 - 299 = 49401$$

About 5% of 6-digit passcodes are triskaidekaphobic

The aforementioned recurrence equation which can be solved to give:

$$n(\mathbb{S}^{(n)}_{\rm unlucky}) = 10^n + \tfrac{(5-2\sqrt{6})^n (5\sqrt{6}-12)-(5+2\sqrt{6})^n (5\sqrt{6}+12)}{24}$$

And the probability of finding an unlucky \(n\)-digit passcode is therefore

$$p(n) = \frac{n(\mathbb{S}^{(n)}_{\rm unlucky})}{n(\mathbb{S}^{(n)})} = 1 + \tfrac{(5-2\sqrt{6})^n (5\sqrt{6}-12)-(5+2\sqrt{6})^n (5\sqrt{6}+12)}{24\times 10^n}$$ Lucky and unlucky passcodes for a triskaidekaphobic person

No. of digits	Unlucky	Lucky	Probability
1	0	10	0%
2	1	99	1%
3	20	980	2%
4	299	9701	2.99%
5	3970	96030	3.97%
6	49401	950599	4.94%
7	590040	9409960	5.9%
8	6850999	93149001	6.85%
\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)

It is also possible to express \(p(n)\) more compactly using finite series. And it is left to the reader to show that,

$$p(n) = 1 + \sum_{k=1}^n \frac{(-1)^k}{10^{2k}}\binom{n-k}{k}$$

With this expression, it is easy to show that \(p(n) < \frac{1}{2}\) for the first time when \(n = 70\), i.e. you are more likely to encounter a lucky passcode if the number of digits in the passcode is more than 70.

But if you are too lazy to figure out all the aforementioned logics, you can actually use the computer to do the math. In tidyverse-styled R, we can write:

library(tidyverse)
passcode <- function(number_of_digits, pattern_input){
  tibble(
    number = 0:(10^number_of_digits - 1),
    passcode = as.character(number),
    pattern = if_else(
      str_detect(passcode, pattern = pattern_input),
      "unlucky",
      "lucky"
    )
  )
}