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
Keywords
Examples
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)
Links
- Kevin Ryde, Table of n, a(n) for n = 1..10000
- Kevin Ryde, Perl and Perl+Foma code to generate the b-file
Crossrefs
Cf. A257371.
Programs
-
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
Extensions
a(26)-a(78) from Kevin Ryde, Jun 02 2020
Comments