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

From ProofWiki
Jump to navigation Jump to search









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$