|
%I #18 Dec 31 2020 16:52:20
%S 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,
%T 31,31,31,31,33,34,34,35,35,35,37,37,37,37,37,37,38,41,40,41,41,49,49,
%U 49,49,49,49,51,52,53,53,55,59,59,59,62,62,63,63,65,65
%N 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
%C 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".
%C 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
%H Kevin Ryde, <a href="/A257371/b257371.txt">Table of n, a(n) for n = 1..10000</a>
%H Kevin Ryde, <a href="/A257371/a257371.pl.txt">Perl program running Foma (or others) to make a b-file</a>
%e From _Kevin Ryde_, Dec 26 2020: (Start)
%e 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.
%e start
%e +===+ 1 +---+ 0 +===+ 1 +===+
%e | A | ---> | B | ---> | C | ---> | D |
%e +===+ <--- +---+ +===+ <--- +===+
%e |0 1 |0 0 ^ |1
%e | +------+ | +-+
%e +-----> | dead | <----+
%e +------+
%e ^ | 0,1
%e +-+
%e (End)
%Y Cf. A004676, A090423, A257291.
%K nonn
%O 1,1
%A _Jeffrey Shallit_, Apr 21 2015
%E a(26)-a(68) from _Kevin Ryde_, Dec 27 2020
|
