The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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 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". 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 LINKS Kevin Ryde, Table of n, a(n) for n = 1..10000 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^* = (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.   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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 24 18:38 EDT 2021. Contains 345419 sequences. (Running on oeis4.)