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

2, 3, 5, 6, 7, 8, 9, 9, 9, 10, 11, 11, 11, 12, 13, 12, 11, 13, 15, 14, 13, 14, 15, 14, 13, 15, 17, 16, 15, 16, 17, 15, 13, 16, 19, 18, 17, 18, 19, 17, 15, 17, 19, 18, 17, 18, 19, 17, 15, 18, 21, 20, 19, 20, 21, 19, 17, 19, 21, 20, 19, 20, 21, 18, 15, 19, 23

Offset

0,1

Links

Table of n, a(n) for n=0..66.

Formula

An empirical formula (unproven):

Case 1: Write n = 2^m + i, 0 <= i < 2^{m-1}, for n>=10.

Then g(n) = g(2^{m-1} + i) +

{ 2, if i=0 or 2^{m-2} <= i < 2^{m-1}

{ 3, if i=1 or i=2^{m-2} - 1

{ 4, if 2<=i<=2^{m-2} - 2.

Case 2: Write n = 2^m + 2^{m-1} + i, 0<= i < 2^{m-1}, for n>=10.

Then g(n) = g(2^m + 2^{m-1} + i) = g(2^m + i) +

{2, if 0 <= i <= 2^{m-1} - 2

{1, if i=2^{m-1}-1.

Crossrefs

Cf. A010060, A382296.

Sequence in context: A280098 A019517 A031976 * A023839 A004723 A293754

Adjacent sequences: A382295 A382296 A382297 * A382299 A382300 A382301

Keyword

nonn

Author

Jeffrey Shallit, Mar 21 2025

Status

approved