login
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
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
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).
Sequence in context: A364104 A050460 A246594 * A334666 A163380 A233569
KEYWORD
nonn,base
AUTHOR
EXTENSIONS
a(23)-a(64) from Thomas Scheuerle, Oct 09 2021
STATUS
approved