A217519 Base-2 state complexity of partitioned deterministic finite automaton (PDFA) for the periodic sequence (123...n)*.

3, 6, 7, 20, 13, 21, 15, 54, 41, 110, 27, 156, 43, 60, 31, 136, 109, 342, 83, 126, 221, 253, 55, 500, 313, 486, 87, 812, 121, 155, 63, 330, 273, 420, 219, 1332, 685, 468, 167, 820, 253, 602, 443, 540, 507, 1081, 111, 1029, 1001, 408, 627, 2756, 973

Offset: 2

Author

N. J. A. Sloane, Oct 07 2012

Keywords

• nonn

Comments

Also the number of infinite words that can be formed from (123..n)* by taking every 2^k-th term from some initial index i, with i and k nonnegative. (Follows from Case 2 of Theorem 2.1) - Charlie Neder, Feb 28 2019

Links

• Charlie Neder, Table of n, a(n) for n = 2..128
• Savinien Kreczman, Luca Prigioniero, Eric Rowland, and Manon Stipulanti, Magic numbers in periodic sequences, arXiv:2304.03268 [cs.FL] (2023).
• Klaus Sutner and Sam Tetruashvili, Inferring Automatic Sequences.

Crossrefs

Cf. A217520, A217521, A247566-A247581, A001122.

Formula

a(2^k) = 2^(k+1) - 1. It appears that a(n) <= n(n-1), with equality if and only if n is a prime with primitive root 2 (A001122). - Charlie Neder, Feb 28 2019

Neder's conjecture was proved by Kreczman, Prigioniero, Rowland, and Stipulanti. - Eric Rowland, Feb 02 2025

Extensions

a(11)-a(20) added (see Inferring Automatic Sequences) by Vincenzo Librandi, Nov 18 2012

a(21)-a(54) from Charlie Neder, Feb 28 2019