# Primes and Subsequences

The Prime Game, Jeff Shallit. There are only finitely many primes that do not have another smaller prime hidden in them as a subsequence of their decimal representations. True more generally for any set instead of "primes" and any base instead of decimal, but for decimal primes Jeff can actually tell you what the minimal ones are.

In terms of finite automata, minimal elements are paths from start to finish which do not selfintersect. For context-free grammars, "paths" are branchy, but selfintersection means center-embedding, so it's forbidden there too. The sets you get by forbidding selfintersection are finite, but they might have "accidental" non-minimal elements. For example "(a+|cat)" has two nonselfintersecting paths "a" and "cat", but "a" is a subsequence of "cat".

Right, so I guess this means that if you substitute a regular (or context free) language for the primes you can find the minimal elements by listing all simple paths (or all expansions without repeated nonterminals) and testing which ones really are minimal.

### Comments:

**atheorist**:

**2006-12-02T23:02:38Z**

In terms of finite automata, minimal elements are paths from start to finish which do not selfintersect. For context-free grammars, "paths" are branchy, but selfintersection means center-embedding, so it's forbidden there too. The sets you get by forbidding selfintersection are finite, but they might have "accidental" non-minimal elements. For example "(a+|cat)" has two nonselfintersecting paths "a" and "cat", but "a" is a subsequence of "cat".

**11011110**:

**2006-12-02T23:41:22Z**

Right, so I guess this means that if you substitute a regular (or context free) language for the primes you can find the minimal elements by listing all simple paths (or all expansions without repeated nonterminals) and testing which ones really are minimal.