A382296 Number of states in smallest DFAO computing t(i+n) on input n in base 2, msd-first, where t(n) = A010060(n), the Thue-Morse sequence.

2, 4, 6, 10, 10, 16, 18, 20, 16, 26, 28, 34, 32, 38, 34, 36, 26, 42, 44, 50, 48, 62, 60, 66, 58, 70, 66, 68, 60, 70, 62, 62, 42, 68, 70, 76, 74, 88, 86, 94, 84, 110, 108, 114, 106, 124, 120, 124, 106, 128, 124, 126, 116, 124, 120, 128, 110, 130, 122, 128, 112

Offset

0,1

Links

Jeffrey Shallit, Table of n, a(n) for n = 0..12000

Delaram Moradi, State Complexity of Linear Relations and Linear Subsequences of Automatic Sequences, Master's Thesis, Univ. Waterloo (Ontario, Canada, 2026). See p. 43.

Delaram Moradi, Narad Rampersad, and Jeffrey Shallit, Complexity of Linear Subsequences of k-Automatic Sequences, arXiv:2512.10017 [cs.FL], 2025. See p. 16.

Formula

It appears from empirical data that a(2^n) = 2*F(n+3), twice the (n+3)'rd Fibonacci number.

Crossrefs

Cf. A000045, A010060, A382298.

Sequence in context: A187333 A321805 A333412 * A376150 A089227 A204660

Adjacent sequences: A382293 A382294 A382295 * A382297 A382298 A382299

Keyword

nonn

Author

Jeffrey Shallit, Mar 21 2025

Extensions

Wrong observation deleted by Jeffrey Shallit, Jan 20 2026

Status

approved