There are 77 Minimal Primes in Base 10 if Single-Digit-Primes Subsequences are Allowed

This article needs to be tidied. In particular: LaTeXify and neaten Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

It has been suggested that this page be renamed. In particular: These are not "minimal primes", that name has already been taken, so we need to define a terminology for exactly what sort of object they are. To discuss this page in more detail, feel free to use the talk page.

This article needs to be linked to other articles. In particular: throughout You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

Theorem

There are $77$ minimal primes in base $10$ if we allow single-digit-primes subsequences (but not allow multidigit-primes subsequences):

$11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$, $59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$, $97$, $227$, $251$, $257$, $277$, $281$, $349$, $409$, $449$, $499$, $521$, $557$, $577$, $587$, $727$, $757$, $787$, $821$, $827$, $857$, $877$, $881$, $887$, $991$, $2087$, $2221$, $5051$, $5081$, $5501$, $5581$, $5801$, $5851$, $6469$, $6949$, $8501$, $9001$, $9049$, $9221$, $9551$, $9649$, $9851$, $9949$, $20 \, 021$, $20 \, 201$, $50 \, 207$, $60 \, 649$, $80 \, 051$, $666 \, 649$, $946 \, 669$, $5 \, 200 \, 007$, $22 \, 000 \, 001$, $60 \, 000 \, 049$, $66 \, 000 \, 049$, $66 \, 600 \, 049$, $80 \, 555 \, 551$, $555 \, 555 \, 555 \, 551$, $5 \, 000 \, 000 \, 000 \, 000 \, 000 \, 000 \, 000 \, 000 \, 000 \, 027$

Proof

In this proof, $x \triangleleft y$ means $x$ is a subsequence of $y$, and $\lambda$ is the empty string.

Assume $p$ is a prime $\gt 10$, and the last digit of $p$ must lie in $\{1,3,7,9\}$ (if the last digit of $p$ is $0$, $2$, $4$, $6$, or $8$, than $p$ is divisible by $2$ (Divisibility by 2), and if the last digit of $p$ is $0$ or $5$, than $p$ is divisible by $5$ (Divisibility by 5)).

Case 1: $p$ ends with $1$

In this case we can write $p = x1$. If $x$ contains $1$, $3$, $4$, $6$, or $7$, then (respectively) $11 \triangleleft p$, $31 \triangleleft p$, $41 \triangleleft p$, $61 \triangleleft p$, or $71 \triangleleft p$. Hence we may assume all digits of $x$ are $0$, $2$, $5$, $8$, or $9$.

Case 1.1: $p$ begins with $2$

In this case we can write $p = 2y1$. If $5 \triangleleft y$, then $251 \triangleleft p$. If $8 \triangleleft y$, then $281 \triangleleft p$. If $9 \triangleleft y$, then $29 \triangleleft p$. Hence we may assume all digits of $y$ are $0$ or $2$.

If $22 \triangleleft y$, then $2221 \triangleleft p$. Hence we may assume $y$ contains zero or one $2$'s.

If $y$ contains no $2$'s, then $p \in 2\{0\}1$. But then, since the sum of the digits of $p$ is $3$, $p$ is divisible by $3$ (Divisibility by 3), so $p$ cannot be prime.

If $y$ contains exactly one $2$, then we can write $p = 2z2w1$, where $z,w \in \{0\}$. If $0 \triangleleft z$ and $0 \triangleleft w$, then $20201 \triangleleft p$. Hence we may assume either $z$ or $w$ is empty.

If $z$ is empty, then $p \in 22\{0\}1$, and the smallest prime $p \in 22\{0\}1$ is $22000001$.

If $w$ is empty, then $p \in 2\{0\}21$, and the smallest prime $p \in 2\{0\}21$ is $20021$.

Case 1.2: $p$ begins with $5$

In this case we can write $p = 5y1$. If $2 \triangleleft y$, then $521 \triangleleft p$. If $9 \triangleleft y$, then $59 \triangleleft p$. Hence we may assume all digits of $y$ are $0$, $5$, or $8$.

If $05 \triangleleft y$, then $5051 \triangleleft p$. If $08 \triangleleft y$, then $5081 \triangleleft p$. If $50 \triangleleft y$, then $5501 \triangleleft p$. If $58 \triangleleft y$, then $5581 \triangleleft p$. If $80 \triangleleft y$, then $5801 \triangleleft p$. If $85 \triangleleft y$, then $5851 \triangleleft p$. Hence we may assume $y \in \{0\} \cup \{5\} \cup \{8\}$.

If $y \in \{0\}$, then $p \in 5\{0\}1$. But then, since the sum of the digits of $p$ is $6$, p is divisible by $3$ (Divisibility by 3), so $p$ cannot be prime.

If $y \in \{5\}$, then $p \in 5\{5\}1$, and the smallest prime $p \in 5\{5\}1$ is $555555555551$.

If $y \in \{8\}$, since if $88 \triangleleft y$, then $881 \triangleleft p$, hence we may assume $y \in \{\lambda,8\}$, and thus $p \in \{51,581\}$, but $51$ and $581$ are both composite.

Case 1.3: $p$ begins with $8$

In this case we can write $p$ = $8y1$. If $2 \triangleleft y$, then $821 \triangleleft p$. If $8 \triangleleft y$, then $881 \triangleleft p$. If $9 \triangleleft y$, then $89 \triangleleft p$. Hence we may assume all digits of $y$ are $0$ or $5$.

If $50 \triangleleft y$, then $8501 \triangleleft p$. Hence we may assume $y \in \{0\}\{5\}$.

If $005 \triangleleft y$, then $80051 \triangleleft p$. Hence we may assume $y \in \{0\} \cup \{5\} \cup 0\{5\}$.

If $y \in \{0\}$, then $p \in 8\{0\}1$. But then, since the sum of the digits of $p$ is $9$, $p$ is divisible by $3$ (Divisibility by 3), so $p$ cannot be prime.

If $y \in \{5\}$, since if $55555555555 \triangleleft y$, then $555555555551 \triangleleft p$, hence we may assume $y \in \{\lambda, 5, 55, 555, 5555, 55555, 555555, 5555555, 55555555, 555555555, 5555555555\}$, and thus $p \in \{81, 851, 8551, 85551, 855551, 8555551, 85555551, 855555551, 8555555551, 85555555551, 855555555551\}$, but all of these numbers are composite.

If $y \in 0\{5\}$, since if $55555555555 \triangleleft y$, then $555555555551 \triangleleft p$, hence we may assume $y \in \{0, 05, 055, 0555, 05555, 055555, 0555555, 05555555, 055555555, 0555555555, 05555555555\}$, and thus $p \in \{801, 8051, 80551, 805551, 8055551, 80555551, 805555551, 8055555551, 80555555551, 805555555551, 8055555555551\}$, and of these numbers only $80555551$ and $8055555551$ are primes, but $80555551 \triangleleft 8055555551$, thus only $80555551$ is minimal prime.

Case 1.4: $p$ begins with $9$

In this case we can write $p = 9y1$. If $9 \triangleleft y$, then $991 \triangleleft p$. Hence we may assume all digits of $y$ are $0$, $2$, $5$, or $8$.

If $00 \triangleleft y$, then $9001 \triangleleft p$. If $22 \triangleleft y$, then $9221 \triangleleft p$. If $55 \triangleleft y$, then $9551 \triangleleft p$. If $88 \triangleleft y$, then $881 \triangleleft p$. Hence we may assume $y$ contains at most one $0$, at most one $2$, at most one $5$, and at most one $8$.

If $y$ only contains at most one $0$ and does not contain any of $\{2,5,8\}$, then $y \in \{\lambda,0\}$, and thus $p \in \{91,901\}$, but $91$ and $901$ are both composite. If $y$ only contains at most one $0$ and only one of $\{2,5,8\}$, then the sum of the digits of $p$ is divisible by $3$, $p$ is divisible by $3$ (Divisibility by 3), so $p$ cannot be prime. Hence we may assume $y$ contains at least two of $\{2,5,8\}$.

If $25 \triangleleft y$, then $251 \triangleleft p$. If $28 \triangleleft y$, then $281 \triangleleft p$. If $52 \triangleleft y$, then $521 \triangleleft p$. If $82 \triangleleft y$, then $821 \triangleleft p$. Hence we may assume $y$ contains no $2$'s (since if $y$ contains $2$, then $y$ cannot contain either $5$'s or $8$'s, which is a contradiction).

If $85 \triangleleft y$, then $9851 \triangleleft p$. Hence we may assume $y \in \{58,580,508,058\}$, and thus $p \in \{9581,95801,95081,90581\}$, and of these numbers only $95801$ is prime, but $95801$ is not minimal prime since $5801 \triangleleft 95801$.

Case 2: $p$ ends with $3$

In this case we can write $p = x3$. If $x$ contains $1$, $2$, $4$, $5$, $7$, or $8$, then (respectively) $13 \triangleleft p$, $23 \triangleleft p$, $43 \triangleleft p$, $53 \triangleleft p$, $73 \triangleleft p$, or $83 \triangleleft p$. Hence we may assume all digits of $x$ are $0$, $3$, $6$, or $9$, and thus all digits of $p$ are $0$, $3$, $6$, or $9$. But then, since the digits of $p$ all have a common factor $3$, $p$ is divisible by $3$ (Numbers with All Digits Have a Common Factor are Divisible by This Factor), so $p$ cannot be prime.

Case 3: $p$ ends with $7$

In this case we can write $p = x7$. If $x$ contains $1$, $3$, $4$, $6$, or $9$, then (respectively) $17 \triangleleft p$, $37 \triangleleft p$, $47 \triangleleft p$, $67 \triangleleft p$, or $97 \triangleleft p$. Hence we may assume all digits of $x$ are $0$, $2$, $5$, $7$, or $8$.

Case 3.1: $p$ begins with $2$

In this case we can write $p = 2y7$. If $2 \triangleleft y$, then $227 \triangleleft p$. If $5 \triangleleft y$, then $257 \triangleleft p$. If $7 \triangleleft y$, then $277 \triangleleft p$. Hence we may assume all digits of $y$ are $0$ or $8$.

If $08 \triangleleft y$, then $2087 \triangleleft p$. If $88 \triangleleft y$, then $887 \triangleleft p$. Hence we may assume $y \in \{0\} \cup 8\{0\}$.

If $y \in \{0\}$, then $p \in 2\{0\}7$. But then, since the sum of the digits of $p$ is $9$, $p$ is divisible by $3$ (Divisibility by 3), so $p$ cannot be prime.

If $y \in 8\{0\}$, then $p \in 28\{0\}7$. But then $p$ is divisible by $7$ (Number of form 28000...0007 is Divisible by 7), since for $n \ge 0$ we have $7 \times 4\underbrace{000 \ldots 000}_{n}1 = 28\underbrace{000 \ldots 000}_{n}7$.

Case 3.2: $p$ begins with $5$

In this case we can write $p = 5y7$. If $5 \triangleleft y$, then $557 \triangleleft p$. If $7 \triangleleft y$, then $577 \triangleleft p$. If $8 \triangleleft y$, then $587 \triangleleft p$. Hence we may assume all digits of $y$ are $0$ or $2$.

If $22 \triangleleft y$, then $227 \triangleleft p$. Hence we may assume $y$ contains zero or one $2$'s.

If $y$ contains no $2$'s, then $p \in 5\{0\}7$. But then, since the sum of the digits of $p$ is $12$, $p$ is divisible by $3$ (Divisibility by 3), so $p$ cannot be prime.

If $y$ contains exactly one $2$, then we can write $p = 5z2w7$, where $z,w \in \{0\}$. If $0 \triangleleft z$ and $0 \triangleleft w$, then $50207 \triangleleft p$. Hence we may assume either $z$ or $w$ is empty.

If $z$ is empty, then $p \in 52\{0\}7$, and the smallest prime $p \in 52\{0\}7$ is $5200007$.

If $w$ is empty, then $p \in 5\{0\}27$, and the smallest prime $p \in 5\{0\}27$ is $5000000000000000000000000000027$.

Case 3.3: $p$ begins with $7$

In this case we can write $p = 7y7$. If $2 \triangleleft y$, then $727 \triangleleft p$. If $5 \triangleleft y$, then $757 \triangleleft p$. If $8 \triangleleft y$, then $787 \triangleleft p$. Hence we may assume all digits of $y$ are $0$ or $7$, and thus all digits of $p$ are $0$ or $7$. But then, since the digits of $p$ all have a common factor $7$, $p$ is divisible by $7$ (Numbers with All Digits Have a Common Factor are Divisible by This Factor), so $p$ cannot be prime.

Case 3.4: $p$ begins with $8$

In this case we can write $p = 8y7$. If $2 \triangleleft y$, then $827 \triangleleft p$. If $5 \triangleleft y$, then $857 \triangleleft p$. If $7 \triangleleft y$, then $877 \triangleleft p$. If $8 \triangleleft y$, then $887 \triangleleft p$. Hence we may assume $y \in \{0\}$, and thus $p \in 8\{0\}7$. But then, since the sum of the digits of $p$ is $15$, $p$ is divisible by $3$ (Divisibility by 3), so $p$ cannot be prime.

Case 4: $p$ ends with $9$

In this case we can write $p = x9$. If $x$ contains $1$, $2$, $5$, $7$, or $8$, then (respectively) $19 \triangleleft p$, $29 \triangleleft p$, $59 \triangleleft p$, $79 \triangleleft p$, or $89 \triangleleft p$. Hence we may assume all digits of $x$ are $0$, $3$, $4$, $6$, or $9$.

If $44 \triangleleft x$, then $449 \triangleleft p$. Hence we may assume $x$ contains zero or one $4$'s.

If $x$ contains no $4$'s, then all digits of $x$ are $0$, $3$, $6$, or $9$, and thus all digits of $p$ are $0$, $3$, $6$, or $9$. But then, since the digits of $p$ all have a common factor $3$, $p$ is divisible by $3$ (Numbers with All Digits Have a Common Factor are Divisible by This Factor), so $p$ cannot be prime. Hence we may assume that $x$ contains exactly one 4.

Case 4.1: $p$ begins with $3$

In this case we can write $p = 3y4z9$, where all digits of $y,z$ are $0$, $3$, $6$, or $9$. We must have $349 \triangleleft p$.

Case 4.2: $p$ begins with $4$

In this case we can write $p = 4y9$, where all digits of $y$ are $0$, $3$, $6$, or $9$. If $0 \triangleleft y$, then $409 \triangleleft p$. If $3 \triangleleft y$, then $43 \triangleleft p$. If $9 \triangleleft y$, then $499 \triangleleft p$. Hence we may assume $y \in \{6\}$, and thus $p \in 4\{6\}9$. But then $p$ is divisible by $7$ (Number of form 4666...6669 is Divisible by 7), since for $n \ge 0$ we have $7 \times \underbrace{666 \ldots 666}_n 7 = 4 \underbrace{666 \ldots 666}_n 9$.

Case 4.3: $p$ begins with $6$

In this case we can write $p = 6y4z9$, where all digits of $y,z$ are $0$, $3$, $6$, or $9$. If $0 \triangleleft z$, then $409 \triangleleft p$. If $3 \triangleleft z$, then $43 \triangleleft p$. If $6 \triangleleft z$, then $6469 \triangleleft p$. If $9 \triangleleft z$, then $499 \triangleleft p$. Hence we may assume $z$ is empty.

If $3 \triangleleft y$, then $349 \triangleleft p$. If $9 \triangleleft y$, then $6949 \triangleleft p$. Hence we may assume all digits of $y$ are $0$ or $6$.

If $06 \triangleleft y$, then $60649 \triangleleft p$. Hence we may assume $y \in \{6\}\{0\}$.

If $666 \triangleleft y$, then $666649 \triangleleft p$. If $00000 \triangleleft y$, then $60000049 \triangleleft p$. Hence we may assume $y \in \{\lambda, 0, 00, 000, 0000, 6, 60, 600, 6000, 60000, 66, 660, 6600, 66000, 660000\}$, and thus $p \in \{649, 6049, 60049, 600049, 6000049, 6649, 66049, 660049, 6600049, 66000049, 66649, 666049, 6660049, 66600049, 666000049\}$, and of these numbers only $66000049$ and $66600049$ are primes.

Case 4.4: $p$ begins with $9$

In this case we can write $p = 9y4z9$, where all digits of $y,z$ are $0$, $3$, $6$, or $9$. If $0 \triangleleft y$, then $9049 \triangleleft p$. If $3 \triangleleft y$, then $349 \triangleleft p$. If $6 \triangleleft y$, then $9649 \triangleleft p$. If $9 \triangleleft y$, then $9949 \triangleleft p$. Hence we may assume $y$ is empty.

If $0 \triangleleft z$, then $409 \triangleleft p$. If $3 \triangleleft z$, then $43 \triangleleft p$. If $9 \triangleleft z$, then $499 \triangleleft p$. Hence we may assume $z \in \{6\}$, and thus $p \in 94\{6\}9$, and the smallest prime $p \in 94\{6\}9$ is $946669$.

$\blacksquare$