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