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.
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".
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.
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.