OFFSET
1,1
COMMENTS
Here by "DFA" we mean "deterministic finite automaton", and by P_n^* we mean the set of all binary strings that can be formed as the concatenation of 0 or more of the base-2 representations of the first n primes. The DFA must be "complete" (there must be a transition for each state and symbol) and hence includes any "dead state".
P_n^* is identical to P_{n-1}^* when prime(n) in binary is the concatenation of smaller primes, since it adds nothing to the pattern. So a(n) = a(n-1) when n in A090423, though various other a(n) = a(m) occur too when different state machines happen to have the same state count. - Kevin Ryde, Dec 26 2020
LINKS
Kevin Ryde, Table of n, a(n) for n = 1..10000
EXAMPLE
From Kevin Ryde, Dec 26 2020: (Start)
For n=3, primes 2,3,5 in binary are 10,11,101 and the regular expression is P_3^* = (10|11|101)*. State machine manipulations, or some thought about these bits, gives the following minimum DFA comprising a(3) = 5 states. States A,C,D are accepting. States B and dead are non-accepting. Dead is reached when some initial part of the input string shows the whole will not match, no matter what follows.
start
+===+ 1 +---+ 0 +===+ 1 +===+
| A | ---> | B | ---> | C | ---> | D |
+===+ <--- +---+ +===+ <--- +===+
|0 1 |0 0 ^ |1
| +------+ | +-+
+-----> | dead | <----+
+------+
^ | 0,1
+-+
(End)
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Apr 21 2015
EXTENSIONS
a(26)-a(68) from Kevin Ryde, Dec 27 2020
STATUS
approved