

A257371


Number of states in minimal DFA for P_n^*, where P_n is the set of base2 representations of the first n prime numbers


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 base2 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_{n1}^* when prime(n) in binary is the concatenation of smaller primes, since it adds nothing to the pattern. So a(n) = a(n1) 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
Kevin Ryde, Perl program running Foma (or others) to make a bfile


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^* = (1011101)*. 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 nonaccepting. 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

Cf. A004676, A090423, A257291.
Sequence in context: A123313 A131507 A203998 * A075260 A054847 A335266
Adjacent sequences: A257368 A257369 A257370 * A257372 A257373 A257374


KEYWORD

nonn


AUTHOR

Jeffrey Shallit, Apr 21 2015


EXTENSIONS

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


STATUS

approved



