Define S(n) as the smallest natural number containing exactly n substrings in its decimal representation which are prime numbers.
Prove that S(n) is defined for each n in N. i.e. for each n in N, there exists a smallest natural number containing exactly n prime substrings.
I am really confused and lost on how to approach this, this has to be done using induction. I wrote the first 6 examples to gain some intuition or see a pattern but it didn't help.
S(0) = ''
S(1) = '2'
S(2) = '13'
S(3) = '23'
S(4) = '113', S(5) = '137', S(6) = '373'
Assuming S(k) is true and there are k substrings containing prime numbers then if i somehow use this to show k + 1, then i would be done but i don't know how i would go about it? Using strong induction didn't help either.
Any hints to point me in the right direction would be much appreciated!
To prove the existence of $S(n)$, firstly note that $\underbrace{22\cdots\cdots2}_{n \text{ times}}$ has exactly $n$ prime substrings. Then the set $$S_n = \{m \in \mathbb{N} \mid \text{$m$ has exactly $n$ prime substrings}\}$$ is not empty for all $n \in \mathbb{N}$. By well ordering principle, stating that every nonempty set of natural numbers contains the least element, $\min S_n$ exists, which is the value you are finding i.e. $S(n) = \min S_n$.