login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=1..6.

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 <iostream>

#include <vector>

// 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<char>& visited) {

  visited[v] = true;

  const uint64_t neighbors[2] = { (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[0] << " k\n";

    return 1;

  }

  const unsigned k = std::atoi(argv[1]);

  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<char> 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.

License Agreements, Terms of Use, Privacy Policy. .

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