A175808 n-th term is the length of a shortest common superstring of the binary representations of all natural numbers from 1 to n.

1, 2, 3, 4, 6, 6, 7, 8, 11, 11, 13, 13, 14, 14, 15, 16, 20, 20, 23, 23, 25, 25, 28, 28, 28, 28, 29, 29, 30, 30, 31, 32, 37, 37, 41, 41, 44, 44, 48, 48, 50, 50, 52, 52, 55, 55, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 61, 61, 62, 62, 63, 64

Offset: 1

Author

Vladimir Reshetnikov, Sep 08 2010

Keywords

• nonn
• base

Comments

If a(n) = 2^m, then we know that the lexicographically largest superstring coincides with the lexicographically largest de Bruijn sequence, B(2,m) (A166316(m)). - Thomas Scheuerle, Oct 09 2021

Examples

			a(5)=6 because 6 is the length of 110100 or 101100, which are the 2 possible shortest common superstrings of 1,10,11,100,101.
		

Crossrefs

Cf. A175809 (number of shortest common superstrings).

Cf. A056744 (least decimal values of shortest common superstrings).

Cf. A166316, A016031.

Formula

It appears that a(2^n-1) = 2^n-1 and a(2^n) = 2^n. - Thomas Scheuerle, Oct 09 2021

Extensions

a(23)-a(64) from Thomas Scheuerle, Oct 09 2021