|
|
A175809
|
|
a(n) is the number of shortest common superstrings of the binary representations of all natural numbers from 1 to n.
|
|
1
|
|
|
1, 1, 1, 1, 2, 2, 2, 2, 6, 4, 6, 4, 16, 16, 16, 16, 84, 56, 120, 108, 216, 108, 1296, 972, 504, 312, 768, 448, 2048, 2048, 2048, 2048
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
COMMENTS
|
All shortest common superstrings share the same number of ones and the same number of substrings of the form "10". If the length of the shortest common superstrings is a power of two (A175808(n) = 2^m), then we know that the lexicographically largest superstring coincides with the lexicographically largest de Bruijn sequence, B(2,m) (A166316(m)). This tells us that in this case all shortest common superstrings contain 2^(m-1) ones in 2^(m-2) groups separated by one or more zeros. - Thomas Scheuerle, Sep 19 2021
|
|
LINKS
|
|
|
FORMULA
|
a(2^n-3) = a(2^n-2) for n > 2. In this case the set of superstrings is equal.
a(2^n-2) = a(2^n-1) = a(2^n) for n > 1. Conjectured. (End)
|
|
EXAMPLE
|
a(5)=2 because there are 2 shortest common superstrings of 1,10,11,100,101; they are 110100 and 101100.
|
|
CROSSREFS
|
Cf. A175808 (length of shortest common superstrings).
Cf. A056744 (least decimal values of shortest common superstrings).
|
|
KEYWORD
|
nonn,base,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|