|
%I #30 Oct 09 2021 00:06:29
%S 1,1,1,1,2,2,2,2,6,4,6,4,16,16,16,16,84,56,120,108,216,108,1296,972,
%T 504,312,768,448,2048,2048,2048,2048
%N a(n) is the number of shortest common superstrings of the binary representations of all natural numbers from 1 to n.
%C 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
%F From _Thomas Scheuerle_, Sep 19 2021: (Start)
%F a(2^n) = A016031(n) (if conjectured A175808(2^n) = 2^n is true).
%F a(2^n-3) = a(2^n-2) for n > 2. In this case the set of superstrings is equal.
%F a(2^n-2) = a(2^n-1) = a(2^n) for n > 1. Conjectured. (End)
%e a(5)=2 because there are 2 shortest common superstrings of 1,10,11,100,101; they are 110100 and 101100.
%Y Cf. A175808 (length of shortest common superstrings).
%Y Cf. A056744 (least decimal values of shortest common superstrings).
%Y Cf. A166316, A016031.
%K nonn,base,more
%O 1,5
%A _Vladimir Reshetnikov_, Sep 08 2010
%E a(21)-a(32) from _Thomas Scheuerle_, Sep 19 2021
|
