cp's OEIS Frontend

A175809 a(n) is the number of shortest common superstrings of the binary representations of all natural numbers from 1 to n.

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