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