cp's OEIS Frontend

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

%I A290772 #27 Feb 01 2022 08:25:46
%S A290772 1,2,24,12,2640,7536,9408,2688,208445760,1082368560,4312566720,
%T A290772 12473296800,24050669760,27034640640,13900259520,1813091520
%N A290772 Number of cyclic Gray codes of length 2n which include all-0 bit sequence and use the least possible number of bits.
%C A290772 From _Andrey Zabolotskiy_, Aug 23 2017: (Start)
%C A290772 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.
%C A290772 A003042 is a subsequence: A003042(n+1) = a(2^n).
%C A290772 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.
%C A290772 (End)
%H A290772 Thomas König, <a href="/A290772/a290772.f90.txt">Fortran program for counting</a>
%e A290772 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:
%e A290772 000, 001, 011, 010, 110, 100
%e A290772 000, 001, 011, 111, 110, 100
%e A290772 000, 001, 011, 111, 110, 010
%e A290772 000, 001, 011, 111, 101, 100
%e A290772 000, 001, 101, 100, 110, 010
%e A290772 000, 001, 101, 111, 110, 100
%e A290772 000, 001, 101, 111, 110, 010
%e A290772 000, 001, 101, 111, 011, 010
%e A290772 000, 010, 011, 001, 101, 100
%e A290772 000, 010, 011, 111, 110, 100
%e A290772 000, 010, 011, 111, 101, 100
%e A290772 000, 010, 011, 111, 101, 001
%e A290772 000, 010, 110, 111, 101, 100
%e A290772 000, 010, 110, 111, 101, 001
%e A290772 000, 010, 110, 111, 011, 001
%e A290772 000, 010, 110, 100, 101, 001
%e A290772 000, 100, 101, 111, 110, 010
%e A290772 000, 100, 101, 111, 011, 010
%e A290772 000, 100, 101, 111, 011, 001
%e A290772 000, 100, 101, 001, 011, 010
%e A290772 000, 100, 110, 111, 101, 001
%e A290772 000, 100, 110, 111, 011, 010
%e A290772 000, 100, 110, 111, 011, 001
%e A290772 000, 100, 110, 010, 011, 001
%o A290772 (Python)
%o A290772 from math import log2, ceil
%o A290772 def cyclic_gray(nb, n, a):
%o A290772     if len(a) == n:
%o A290772         if bin(a[-1]).count('1') == 1:
%o A290772             return 1
%o A290772         return 0
%o A290772     r = 0
%o A290772     for i in range(nb):
%o A290772         x = a[-1] ^ (1<<i)
%o A290772         if x not in a:
%o A290772             r += cyclic_gray(nb, n, a+[x])
%o A290772     return r
%o A290772 print([cyclic_gray(ceil(log2(n))+1, n*2, [0]) for n in range(1, 9)])
%o A290772 # _Andrey Zabolotskiy_, Aug 23 2017
%Y A290772 Cf. A003042, A286899, A350784.
%K A290772 nonn,hard,more
%O A290772 1,2
%A A290772 _Ashis Kumar Mal_, Aug 10 2017
%E A290772 a(7)-a(8) and name from _Andrey Zabolotskiy_, Aug 23 2017
%E A290772 a(9)-a(13) from _Ashis Kumar Mal_, Sep 02 2017
%E A290772 a(14)-a(16) from _Thomas König_, Jan 22 2022