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

Author

Ashis Kumar Mal, Aug 10 2017

Keywords

• nonn
• hard
• more

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)

Examples

			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
		

Links

• Thomas König, Fortran program for counting

Crossrefs

Cf. A003042, A286899, A350784.

Programs

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<Andrey Zabolotskiy, Aug 23 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