A290772 Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits.

1, 2, 24, 12, 2640, 7536, 9408, 2688, 208445760, 1082368560, 4312566720, 12473296800, 24050669760, 27034640640, 13900259520, 1813091520

Offset

1,2

Comments

From Andrey Zabolotskiy, Aug 23 2017: (Start)

The smallest number of bits needed is ceiling(log_2(n)). For larger number of bits, more Gray codes exist. Cyclic Gray codes of odd lengths do not exist, hence only even lengths are considered.

A003042 is a subsequence: A003042(n+1) = a(2^n).

a(n) is also the number of self-avoiding directed cycles of length 2n on a cube of the least possible dimension starting from the origin.

(End)

Links

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

Thomas König, Fortran program for counting

Example

Let n=3, so we count codes of length 6. Then at least 3 bits are needed to have such a code. There are a(3)=24 3-bit cyclic Gray codes of length 6:
000, 001, 011, 010, 110, 100
000, 001, 011, 111, 110, 100
000, 001, 011, 111, 110, 010
000, 001, 011, 111, 101, 100
000, 001, 101, 100, 110, 010
000, 001, 101, 111, 110, 100
000, 001, 101, 111, 110, 010
000, 001, 101, 111, 011, 010
000, 010, 011, 001, 101, 100
000, 010, 011, 111, 110, 100
000, 010, 011, 111, 101, 100
000, 010, 011, 111, 101, 001
000, 010, 110, 111, 101, 100
000, 010, 110, 111, 101, 001
000, 010, 110, 111, 011, 001
000, 010, 110, 100, 101, 001
000, 100, 101, 111, 110, 010
000, 100, 101, 111, 011, 010
000, 100, 101, 111, 011, 001
000, 100, 101, 001, 011, 010
000, 100, 110, 111, 101, 001
000, 100, 110, 111, 011, 010
000, 100, 110, 111, 011, 001
000, 100, 110, 010, 011, 001

Prog

(Python)
from math import log2, ceil
def cyclic_gray(nb, n, a):
    if len(a) == n:
        if bin(a[-1]).count('1') == 1:
            return 1
        return 0
    r = 0
    for i in range(nb):
        x = a[-1] ^ (1<<i)
        if x not in a:
            r += cyclic_gray(nb, n, a+[x])
    return r
print([cyclic_gray(ceil(log2(n))+1, n*2, [0]) for n in range(1, 9)])
# Andrey Zabolotskiy, Aug 23 2017

Crossrefs

Cf. A003042, A286899, A350784.

Sequence in context: A075267 A002743 A220773 * A342545 A055535 A072217

Adjacent sequences: A290769 A290770 A290771 * A290773 A290774 A290775

Keyword

nonn,hard,more

Author

Ashis Kumar Mal, Aug 10 2017

Extensions

a(7)-a(8) and name from Andrey Zabolotskiy, Aug 23 2017

a(9)-a(13) from Ashis Kumar Mal, Sep 02 2017

a(14)-a(16) from Thomas König, Jan 22 2022

Status

approved