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,2

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

Links

Table of n, a(n) for n=1..64.

Formula

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

Example

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.

Sequence in context: A050460 A379108 A246594 * A334666 A163380 A233569

Adjacent sequences: A175805 A175806 A175807 * A175809 A175810 A175811

Keyword

nonn,base

Author

Vladimir Reshetnikov, Sep 08 2010

Extensions

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

Status

approved