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

%I #27 Feb 01 2022 08:25:46

%S 1,2,24,12,2640,7536,9408,2688,208445760,1082368560,4312566720,

%T 12473296800,24050669760,27034640640,13900259520,1813091520

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

%C From _Andrey Zabolotskiy_, Aug 23 2017: (Start)

%C 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 A003042 is a subsequence: A003042(n+1) = a(2^n).

%C 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 (End)

%H Thomas König, <a href="/A290772/a290772.f90.txt">Fortran program for counting</a>

%e 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 000, 001, 011, 010, 110, 100

%e 000, 001, 011, 111, 110, 100

%e 000, 001, 011, 111, 110, 010

%e 000, 001, 011, 111, 101, 100

%e 000, 001, 101, 100, 110, 010

%e 000, 001, 101, 111, 110, 100

%e 000, 001, 101, 111, 110, 010

%e 000, 001, 101, 111, 011, 010

%e 000, 010, 011, 001, 101, 100

%e 000, 010, 011, 111, 110, 100

%e 000, 010, 011, 111, 101, 100

%e 000, 010, 011, 111, 101, 001

%e 000, 010, 110, 111, 101, 100

%e 000, 010, 110, 111, 101, 001

%e 000, 010, 110, 111, 011, 001

%e 000, 010, 110, 100, 101, 001

%e 000, 100, 101, 111, 110, 010

%e 000, 100, 101, 111, 011, 010

%e 000, 100, 101, 111, 011, 001

%e 000, 100, 101, 001, 011, 010

%e 000, 100, 110, 111, 101, 001

%e 000, 100, 110, 111, 011, 010

%e 000, 100, 110, 111, 011, 001

%e 000, 100, 110, 010, 011, 001

%o (Python)

%o from math import log2, ceil

%o def cyclic_gray(nb, n, a):

%o if len(a) == n:

%o if bin(a[-1]).count('1') == 1:

%o return 1

%o return 0

%o r = 0

%o for i in range(nb):

%o x = a[-1] ^ (1<<i)

%o if x not in a:

%o r += cyclic_gray(nb, n, a+[x])

%o return r

%o print([cyclic_gray(ceil(log2(n))+1, n*2, [0]) for n in range(1, 9)])

%o # _Andrey Zabolotskiy_, Aug 23 2017

%Y Cf. A003042, A286899, A350784.

%K nonn,hard,more

%O 1,2

%A _Ashis Kumar Mal_, Aug 10 2017

%E a(7)-a(8) and name from _Andrey Zabolotskiy_, Aug 23 2017

%E a(9)-a(13) from _Ashis Kumar Mal_, Sep 02 2017

%E a(14)-a(16) from _Thomas König_, Jan 22 2022