cp's OEIS Frontend

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.

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