login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A175809 a(n) is the number of shortest common superstrings of the binary representations of all natural numbers from 1 to n. 1

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 5 09:25 EST 2023. Contains 360084 sequences. (Running on oeis4.)