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!)
A058052 Sum of the distances between the 2^n vertices in the De Bruijn Graphs on words of length n on alphabet {0,1}. 0
2, 18, 118, 680, 3620, 18274, 88760, 418900, 1933904, 8775534, 39277136, 173843142, 762388102, 3317784992, 14344443516, 61671799608, 263865053452, 1124175400716, 4771570406736, 20185774001256, 85141101913670 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,1
COMMENTS
Given two words X,Y in {0,1}^N, the distance d(X,Y) is the least integer K such that there exists a word M with X=UM and Y=MV and |U|=|V|=K. Define a(N)=sum(d(X,Y); X,Y in {0,1}^N).
LINKS
Eric Weisstein's World of Mathematics, de Bruijn Sequence.
EXAMPLE
d(0,0)=0, d(0,1)=1, d(1,0)=1, d(1,1)=0, hence a(1)=0+1+1+0=2.
d(00,00)=0, d(00,01)=1, d(00,10)=2, d(00,11)=2, d(01,00)=2, d(01,01)=0, d(01,10)=1, d(01,11)=1, d(10,00)=1, d(10,01)=1, d(10,10)=0, d(10,11)=2, d(11,00)=2, d(11,01)=2, d(11,10)=1, d(11,11)=0, hence a(2)=0+1+2+2+2+0+1+1+1+1+0+2+2+2+1+0=18.
PROG
(Python)
from numba import njit
@njit
def d(x, y, n):
for k in range(n):
mask = (1 << (n-k)) - 1
if x & mask == (y >> k): return k
return n
@njit
def a(n):
s = 0
for x in range(2**(n-1)):
for y in range(2**n):
s += d(x, y, n)
return 2*s
print([a(n) for n in range(1, 15)]) # Michael S. Branicky, Feb 18 2021
CROSSREFS
Cf. A166316.
Sequence in context: A027433 A153338 A007798 * A119578 A052610 A052653
KEYWORD
nonn
AUTHOR
Serge Burckel (burckel(AT)iml.univ-mrs.fr), Nov 19 2000
EXTENSIONS
a(9)-a(21) from Michael S. Branicky, Feb 18 2021
STATUS
approved

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 April 23 23:26 EDT 2024. Contains 371917 sequences. (Running on oeis4.)