$\mathbf{Question:}$
Define $P(n)$ as the smallest natural number containing exactly $n$ substrings in its decimal representation which are prime numbers.
For example, $P(2) = 13$, because the string '13' contains the prime numbers 3 and 13 itself (and is smaller than any other number with this
property, such as 31).
$P(6) = 373$, corresponding to the prime numbers 3 (which appears twice), 7, 37, 73, and 373.
Also, note that the substrings starts with 0 does not count (for example: the string '103' has two prime numbers in total, since, 103 itself and 3 are prime numbers and '03' does not count as a prime number.)
$\mathbf{Want~to~Prove:}$ $\forall n \in \mathbb{N}$, $P(n)$ holds,
i.e. $\forall n \in \mathbb{N}$, there exists a smallest natural number containing exactly $n$ prime substrings. (The prove must using Induction)
$\mathbf{My Thought:}$ Well I wrote a program that check through strings from P(1) to P(27).
Which P(1) is 2; P(2) is 13; P(3) is 23; P(4) is 113; P(5) is 137; P(6) is 373; P(7) is 1137; P(8) is 1733; P(9) is 1373;
P(10) is 11317; P(11) is 11373; P(12) is 13733; P(13) is 31373;
P(14) is 113173; P(15) is 131373; P(16) is 137337;
P(17) is 337397; P(18) is 1113173; P(19) is 1137337;
P(20) is 1373373; P(21) is 2337397; P(22) is 3733797;
P(23) is 11373137; P(24) is 11373379; P(25) is 13733797;
P(26) is 37337397; P(27) is 111373379; ...
The only pattern I found is that the number strings above can only contain 1,2,3,7,9
Also, I notice that if $d$ is number of digits for each natural number string $P(n)$ then $n <= \frac{d(d+1)}{2}$. (but I think this is quite unrelated for proving $P(n)$)
Well, the another way I throught is that I can probably use a structural induction on the string $P(n)$. base on a starting string $s$ that is a prime and keep adding characters 1,2,3,7, or 9 on the back of $s$. but this throught is still to vac because I cannot find any general pattern base on that as well.
So, I am quite stuck on either structural induction on string $P(n)$ or the induction on the number $n$.
Well, are there any hints for this question, or some theorems I can apply for this prove this question ??
If $P(k)$ has exactly $k$ substrings in its decimal representation which are prime numbers, then
$$10P(k)+2$$
has exactly $k+1$ substrings in its decimal representation which are prime numbers.
It may not be the smallest, but at least such $P(k+1)$ exists.
This is given that, as in your example of $P(6)$, different substrings of prime numbers can map to equal prime number.