A257291 Number of states in minimal DFA accepting base-2 representation of first n prime numbers.

4, 4, 5, 5, 6, 8, 9, 9, 10, 11, 11, 12, 13, 13, 14, 16, 17, 17, 19, 20, 21, 21, 21, 22, 23, 23, 24, 24, 24, 25, 26, 27, 28, 28, 29, 29, 31, 32, 33, 35, 36, 36, 37, 38, 38, 38, 39, 40, 41, 40, 41, 41, 42, 43, 44, 44, 44, 45, 46, 46, 47, 47, 48, 48, 49, 49, 49, 51, 52, 52, 54, 55, 55, 56, 56, 57, 58, 58

Offset

1,1

Comments

By "DFA" we mean deterministic finite automaton, which must be "complete" (that is, a transition must exist for every state). So the minimal DFA for n = 1 corresponds to a DFA that accepts the string "10" and no other. Four states are required since a "dead state" is also needed.

Links

Kevin Ryde, Table of n, a(n) for n = 1..10000

Kevin Ryde, Perl and Perl+Foma code to generate the b-file

Example

From Kevin Ryde, Jun 02 2020: (Start)
For n=3, the minimum DFA comprises a(3) = 5 states:
                            +------------------------+
     start                1 |                        v
  +-----------+  1   +--------+  0   +=====+  1   +=====+
  | 10,11,101 | ---> | 0,1,01 | ---> | e,1 | ---> |  e  |
  +-----------+      +--------+      +=====+      +=====+
        | 0                             | 0          | 0,1
        |                               |            v
        |                               |        +------+
        +-------------------------------+------> | dead |
                                                 +------+
                                                   ^ | 0,1
                                                   +-+
Each state is a set of bit strings wanted.  The start state is primes 2,3,5 in binary.  Each "1" transition takes strings starting 1 and removes that 1.  Each 0 transition similarly.  "e" is the empty string.  Each state containing "e" is accepting because it's the end of one of the original primes.  "Dead" is the set of no strings and is a non-accepting sink.  Input strings too long or not a prefix of one of the desired primes end up at dead.
(End)

Prog

(PARI) a(n) = {
  my(m=Map(), q=List([apply(p->Vecsmall(binary(p)), primes(n))]));
  while(#q, my(s=q[#q]); listpop(q);
    if(!mapisdefined(m, s), mapput(m, s, 1);
      for(i=0, 1, listput(q, apply(v->v[^1],
                             select(v->#v&&v[1]==i, s))))));
  #m; }  \\ Kevin Ryde, Jun 02 2020
(Python)
from sympy import prime, primerange
def a(n):
    m = dict()
    q = [tuple(bin(p)[2:] for p in primerange(1, prime(n)+1))]
    while len(q) > 0:
        s = q.pop()
        if s not in m:
            m[s] = 1
            for i in "01":
                q.append(tuple(v[1:] for v in s if len(v) and v[0]==i))
    return len(m)
print([a(n) for n in range(1, 80)]) # Michael S. Branicky, Jul 04 2022 after Kevin Ryde

Crossrefs

Cf. A257371.

Sequence in context: A003869 A065864 A120205 * A152465 A357414 A082968

Adjacent sequences: A257288 A257289 A257290 * A257292 A257293 A257294

Keyword

nonn

Author

Jeffrey Shallit, Apr 21 2015

Extensions

a(26)-a(78) from Kevin Ryde, Jun 02 2020

Status

approved