A058052 - OEIS

%I #9 Feb 18 2021 12:46:20

%S 2,18,118,680,3620,18274,88760,418900,1933904,8775534,39277136,

%T 173843142,762388102,3317784992,14344443516,61671799608,263865053452,

%U 1124175400716,4771570406736,20185774001256,85141101913670

%N Sum of the distances between the 2^n vertices in the De Bruijn Graphs on words of length n on alphabet {0,1}.

%C 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).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/deBruijnSequence.html">de Bruijn Sequence</a>.

%e d(0,0)=0, d(0,1)=1, d(1,0)=1, d(1,1)=0, hence a(1)=0+1+1+0=2.

%e 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.

%o (Python)

%o from numba import njit

%o @njit

%o def d(x, y, n):

%o   for k in range(n):

%o     mask = (1 << (n-k)) - 1

%o     if x & mask == (y >> k): return k

%o   return n

%o @njit

%o def a(n):

%o   s = 0

%o   for x in range(2**(n-1)):

%o     for y in range(2**n):

%o       s += d(x, y, n)

%o   return 2*s

%o print([a(n) for n in range(1, 15)]) # _Michael S. Branicky_, Feb 18 2021

%Y Cf. A166316.

%K nonn

%O 1,1

%A Serge Burckel (burckel(AT)iml.univ-mrs.fr), Nov 19 2000

%E a(9)-a(21) from _Michael S. Branicky_, Feb 18 2021