A151998 Directed genus of the binary de Bruijn graph D_n.

0, 0, 0, 1, 2, 7, 15, 35, 75, 163, 337, 709, 1458, 3001, 6135, 12529, 25468, 51739, 104829, 212205, 428916, 866215, 1747527, 3523213, 7097895, 14291683, 28760643, 57852469, 116321445, 233798623, 469761015, 943591237, 1894836585, 3804113881, 7635493643

Offset

0,5

Links

Table of n, a(n) for n=0..34.

A. W. Hales and N. Hartsfield, The directed genus of the de Bruijn graph, Discrete Math., 309 (2009), 5259-5263.

Formula

See Maple code.

Maple

with(numtheory);
f:=proc(n) local t1, t2, t3, i;
t1:=divisors(n+2); t2:=convert(t1, list);
t3:=add( phi(t2[i])*2^((n+2)/t2[i]), i =1..nops(t2));
2^(n-1) + 1 - t3/(2*(n+2));
end;

Prog

(PARI) a(n) = 2^(n-1) + 1 - sumdiv(n+2, d, 2^((n+2)/d)*eulerphi(d))/(2*(n+2)); \\ Michel Marcus, Mar 02 2019

Crossrefs

Sequence in context: A209633 A216633 A295145 * A308631 A052130 A366130

Adjacent sequences: A151995 A151996 A151997 * A151999 A152000 A152001

Keyword

nonn

Author

N. J. A. Sloane, Sep 15 2009

Status

approved