This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A306522 Number of simple directed cycles in the binary de Bruijn graphs of order n. 0
 3, 6, 19, 179, 30176, 1202267287 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,1 COMMENTS The numbers are computed empirically by the C++ program below. For n=7, the value is > 144*10^15 (the number of Hamiltonian cycles, A016031). LINKS EXAMPLE For n=1, the cycles are (0), (1) and (0, 1). For n=2, the cycles are (00), (00, 01, 10), (00, 01, 11, 10), (01, 10), (01, 11, 10), (11). PROG (C++) #include #include // DFS for binary de Bruijn graph. Count cycles starting at start, and // don't visit cycles with nodes v < start, to avoid double counting // any cycle. uint64_t cycles_visit(uint64_t mask, uint64_t start, uint64_t v, std::vector& visited) {   visited[v] = true;   const uint64_t neighbors = { (v << 1) & mask, ((v << 1) & mask) | 1 };   uint64_t count = 0;   for(uint64_t n : neighbors) {     if(n < start) continue;     if(visited[n]) {       if(n == start)         ++count;     } else {         count += cycles_visit(mask, start, n, visited);     }   }   visited[v] = false;   return count; } int main(int argc, char *argv[]) {   if(argc != 2) {     std::cerr << "Usage: " << argv << " k\n";     return 1;   }   const unsigned k = std::atoi(argv);   const uint64_t mask = ((uint64_t)1 << k) - 1;   if(k == 1) { // Optimization below does not work for k==1     std::cout << 3 << '\n';     return 0;   }   std::vector visited(mask+1, false);   // Cycles starting with 0...01   uint64_t total = cycles_visit(mask, 1, 1, visited);   // Cycles containing  0...0 also contain 0...01, except for the self loop 0...0   total += total + 1;   // Start from all other nodes   for(uint64_t v = 2; v < mask; ++v) {     total += cycles_visit(mask, v, v, visited);   }   total += 1; // self loop 1...1   std::cout << total << '\n';   return 0; } CROSSREFS Sequence in context: A184937 A215817 A269306 * A290784 A176993 A276748 Adjacent sequences:  A306518 A306519 A306520 * A306523 A306524 A306525 KEYWORD nonn,hard,more AUTHOR Guillaume Marçais, Feb 21 2019 STATUS approved

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

Last modified May 23 11:05 EDT 2019. Contains 323513 sequences. (Running on oeis4.)