A257371 Number of states in minimal DFA for P_n^*, where P_n is the set of base-2 representations of the first n prime numbers.

3, 3, 5, 5, 5, 7, 8, 8, 8, 8, 8, 9, 12, 12, 12, 15, 15, 15, 17, 17, 18, 18, 18, 19, 29, 29, 31, 31, 31, 31, 31, 33, 34, 34, 35, 35, 35, 37, 37, 37, 37, 37, 37, 38, 41, 40, 41, 41, 49, 49, 49, 49, 49, 49, 51, 52, 53, 53, 55, 59, 59, 59, 62, 62, 63, 63, 65, 65

Offset: 1

Author

Jeffrey Shallit, Apr 21 2015

Keywords

• nonn

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

Examples

			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)
		

Links

• Kevin Ryde, Table of n, a(n) for n = 1..10000
• Kevin Ryde, Perl program running Foma (or others) to make a b-file

Crossrefs

Cf. A004676, A090423, A257291.

Extensions

a(26)-a(68) from Kevin Ryde, Dec 27 2020